Daedalus, tired of his job as Shop teacher, accepts an invitation from King Minos (Charles Nelson Reilly) to come to Crete and build him a Labyrinth, which is to be a wonder of the world. He and Icarus travel to the island where they discover that it is being built to hold the Minotaur (Michael Dorn), a savage half-man, half-bull. Meanwhile in Athens, Hercules accepts a challenge to fight the Minotaur and also travels to Crete, unaware of the fact the Labyrinth is a maze which one can only escape from by means of magic yarn. Icarus throws him some, but ends up throwing it (and himself) straight at the Minotaur. Daedalus defies Minos and takes command of his giant robot, just as the Minotaur escapes. Hercules comes to his aid just in time, tossing the Minotaur back into the maze where Minos is trying to navigate it. Hercules, Icarus and Daedalus are rescued by Cassandra and the rest of Shop class in Daedalus' flying machine.