The film begins with Hercules at Olympus, berating his father Zeus for not allowing him to leave the Gods' abode to adventure on earth. Eventually Zeus tires of Hercules and blasts him with a lightning bolt, casting him out of Olympus - giving Hercules what he wanted.
After some strange encounters in the air and at sea, Hercules arrives in New York City, where hilarity ensues in the form of interactions with various New Yorkers, who regard him as physically superior but socially awkward. He meets a skinny little guy called Pretzie. Hercules becomes a successful proffesional wrestler.
Zeus, watching Hercules from the heights, becomes irritated with Hercules' antics, which he feels are making a mockery of the Gods, and calls on Mercury to stop Hercules. After Mercury makes an unsuccessful attempt to bring Hercules home, Zeus orders Nemesis to see to it that Hercules is consigned to the infernal regions ruled over by Pluto.
However, Juno instead convinces Nemesis to poison Hercules with a poison that would strip him of his divinity and then talk to Pluto. Nemesis informs Pluto of what is happening and he bets a large sum of money against Hercules in an upcoming strongman competition with Hercules' gangster manager.
When Hercules loses the strongman competition his friends try to lead off Hercules' angry manager's henchmen, but Hercules follows them to save them.
Meanwhile, Zeus uncovers the truth from Nemesis as to what is happening but only intervenes at the last minute to restore Hercules divinity not wanting any son of his to die at the hands of a mortal.
Hercules defeats the gangsters and realizes that he has been disobedient and returns to the heavens shortly after, only saying good-bye to Pretzie over a radio after he left.
In the heavens, Zeus tells Juno and Hercules that he is not going to decide what to do about what happened as they ask him about it and asks to be left alone. They leave him alone, and upon their departure, Zeus sneaks out of the heavens and descends to earth, scaring a passenger jet on his way down.