Sinbad (Patrick Wayne), sailor and Prince of Baghdad, moors at Charak, intent on seeking permission from Prince Kassim to marry Kassim's sister, Princess Farah (Jane Seymour). He quickly gets used to the city and its people, but finds it under curfew. When he shelters in a nearby tent, a witch (whom the audience later learns is Zenobia) summons a trio of ghouls, which emerge from a fire. Sinbad disposes of the ghouls. Meanwhile, Farah and Kassim's evil stepmother, Zenobia (Margaret Whiting), turn Kassim into a baboon (one of Harryhausen's stop-motion creations) just as he was going to be crowned caliph. If Kassim cannot regain his human form within seven moons, then Zenobia's son Rafi will be caliph instead.
Sinbad meets with Farah, who believes Kassim's curse is one of Zenobia's spells. Sinbad, Farah, and the baboon Kassim set off to find the old Greek alchemist named Melanthius (Patrick Troughton), a hermit of on the island of Casgar, who is said to know how to break the spell. Zenobia and her son, Rafi (Kurt Christian), follow in a boat propelled by the robotic bronze Minoton, a magical creature created by the sorceress which looks like a Minotaur. During the voyage, Farah proves to be the only person capable of calming the baboon. Sinbad is convinced that the baboon is Kassim after he witnesses it playing chess with Farah.
Sinbad and Farah land at Casgar and find Melanthius and his daughter Dione (Taryn Power), who agree to help them. Melanthius says they must travel to the land of Hyperborea where the ancient civilization of the Arimaspi once existed. On the way to Hyperborea, Melanthius and Dione also become convinced that the baboon is Kassim.
Zenobia uses a potion to transform herself into a gull to spy on Sinbad. Once aboard his ship, she turns into a miniature human and listens in as Melanthius tells Sinbad how to cure Kassim. Alerted by Kassim, Melanthius and Sinbad capture Zenobia. Unfortunately, her potion spills and a wasp ingests some of it. The wasp grows to enormous size and attacks the two men, but Sinbad kills it with a knife. Zenobia takes what is left of her potion, turns into a gull, and flies back to her own ship. But there is too little of the drink left: While Zenobia is restored to human form and full size, the lower part of her right leg looks like a gull's foot.
After a long voyage, Sinbad's ship reaches the north polar wastes. Sinbad and his crew trek across the ice to the land of the Arimaspi, but are attacked by a giant walrus. It destroys most of their supplies and kills two men, but Sinbad and the others fend it off with spears. Zenobia uses an ice tunnel to reach the land of the Arimaspi, and she, Rafi, and the Minoton climb subterranean stairs to emerge in the warm, Mediterranean-like valley above.
Sinbad and his crew also reach the valley. While resting, they encounter a troglodyte a 12-foot (3.7Â m) tall creature somewhat like a fur-covered caveman, with a single horn coming out of the top of its head. The troglodyte proves not dangerous, but rather friendly and follows the adventurers to the giant pyramidal shrine of the Arimaspi. Zenobia and Rafi arrive at the shrine first, but she has no key to enter. She orders the Minoton to remove a block of stone from the pyramid's wall. He succeeds, but the block crushes the Minoton and destabilizes the shrine's power.
Sinbad and his friends arrive minutes later, and realize Zenobia has entered the pyramid. They enter the shrine's main chamber, the interior of which is covered in ice. The shrine is guarded by a saber-toothed tiger frozen in a block of ice. Rafi attacks Melanthius with a knife, but he is attacked by Kassim and is killed falling down the temple stairs. Momentarily overcome with grief, Zenobia cradles her son while Sinbad and Melanthius investigate how to get Kassim into the column of light at the top of the shrine which will break the spell. Having come to her senses again, Zenobia transfers her spirit into the saber-toothed tiger. Breaking free of its icy prison, the cat attacks Sinbad and his men. The troglodyte then enters the scene and engages the saber-toothed tiger in combat. Initially gaining the upper hand and even slamming the beast to the ground, the saber-toothed tiger disarms the troglodyte of its spear and pins it to the wall, inflicting more damage before killing it via biting the neck. Maroof is then slain. The saber-toothed tiger then attacks Sinbad, who kills it with a spear. The spell on Kassim is broken, and the adventurers flee the temple as it collapses about them.
Sinbad, Kassim, Farah, Melanthius, and Dione and return home just in time for Kassim to be crowned Caliph. Sinbad and Farah share a kiss. The film fades to black, and the eyes of Zenobia appear on the screen.
What insect grew to an enormous size?
A wasp