The story begins when Zeus (Homer Simpson) knocks his box of lightning bolts off of the edge of the railing and the lightning bolts fall to Earth, zapping Sodom and Gomorrah. Hera (Marge Simpson) questions Zeus's whereabouts the night before after seeing feathers and an egg in Zeus's chair, claiming that he turned into a swan and went to the singles bar. Zeus tells Hera he did some "harmless flirting" but claims nothing more happened. Next, Hercules (Bart Simpson) appears, saying that he is Zeus's illegitimate son, resulting in a "D'oh!" from Zeus. Hera forces Hercules to do "twelve labors" while Zeus sits in his chair. Grampa asks Zeus if he can return, but is denied after Grampa ate Zeus when Zeus was Hercules's age. Meanwhile, Hercules goes out and is robbed by the Hydra (Snake), prompting Hercules to attack. He slashes at Hydra, but Hydra's heads multiply with each slash. When Hercules asks which of Hydra's heads wants his money, they all get into a fight and Hercules escapes unharmed.
Later, Hercules has to clean the Augean stables when Mr. Burns and his servant (Smithers) pass by with bags of money. He tells Burns that gold is worthless and that the "dung mine" (the Augean stables) is worth a fortune. Burns agrees to trade gold, his horse, and the deed to his home for Hercules's "dung mine." Hercules then leaves as Burns and his servant are digging "dung" in just their sandals and underwear. When Hercules gets back, he gives Hermes (Milhouse) a message to the Grecian SPCA with a list of unlicense and possibly rabid animals. Chief Wiggum rounds up all of the animals, and Jessica Lovejoy wants to adopt the minotaur, but Reverend Lovejoy reminds her that the minotaur comes with responsibilities.
When Hercules returns to Hera, he has done only ten of the twelve labors, and tells Hera that ten out of twelve is a "B+." Hercules encourages Hera to take over for Zeus and be the one running things. Eventually, the plan backfires, as Hera forces the kids to do labors (and Nelson saying "Way to go Jerk-ules!").