While sailing, Sinbad comes across a golden tablet dropped by a mysterious flying creature. He wears the tablet as an amulet around his neck. That night, Sinbad has a strange dream in which he sees a man dressed in black, repeatedly calling Sinbad's name, and also about a mysterious girl with an eye tattooed on her right palm. During his sleep, a mysterious storm throws his ship off course, and the next day Sinbad and his men find themselves near a coastal town in the country of Marabia.
Swimming to the beach, Sinbad is met by a dark-cloaked man, who demands his amulet. Sinbad narrowly escapes into the city, where the city guard forces the hostile stranger to flee. Soon, Sinbad encounters the Grand Vizier of Marabia (Douglas Wilmer). The Vizier, who wears a golden mask to hide his disfigured face, says that Sinbad's amulet is actually one piece of a puzzle; the Vizier has another. The Vizier relates to Sinbad a legend that the three pieces, when joined together, will reveal a map showing the way to the Fountain of Destiny, hidden somewhere on the lost continent of Lemuria. The legend tells that he who bears the three pieces of the puzzle to the fountain will receive "youth, a shield of darkness, and a crown of untold riches."
Sinbad agrees to help the Vizier find the fountain. They join forces against Prince Koura (Tom Baker), the black-cloaked man who is an evil magician bent on conquering Marabia. Koura had locked the Vizier in a room and set it on fire, horribly burning his face. The creature that dropped the gold tablet was one of Koura's minions, a homunculus created by his black magic. Using this creature he hears the conversation, and it turns to ash when it is found.
Shortly afterward, Sinbad meets the girl he saw in his dream, Margiana (Caroline Munro), a slave-girl. Her master hires Sinbad to make a man of his lazy, no-good son Haroun (Kurt Christian), and Sinbad agrees on the condition that Margiana goes with him; so the two new passengers and the Vizier board Sinbad's ship. Koura hires a ship and crew of his own and follows Sinbad, using his magic several times to try to stop Sinbad. However, each attempt drains away part of his life force and he ages noticeably each time.
Along his journey, Sinbad fights the wooden siren figurehead from his own ship which Koura has animated, which steals the map, enabling Koura to find the Island. However Sinbad has memorised the map. Koura gets to the Island and uses another homunculus to hear the Oracle of All Knowledge (an uncredited Robert Shaw) as it describes to Sinbad what he will face. Koura then seals the men inside the cave, however Sinbad is able to escape with a rope and get the others out. The Homunculus is killed with an arrow as it tries to stop Sinbad. Koura animates a six-armed Kali idol when he is captured by hostile natives, causing them to free him. However, Sinbad and his men arrive and fight and defeat Kali. The natives capture Sinbad and his crew and give Margiana to a one-eyed centaur, the fountain's guardian of evil. Sinbad and the others escape when the Vizier shows his burnt face, scaring the natives. The Centaur fights (and kills) the guardian of good, a griffin, with Koura's help, however Sinbad then stabs it dead. Once they reach the fountain, Koura obtains all the pieces, assembles the puzzle, and drops it in the fountain. His health is restored and he becomes invisible (the "shield of darkness"). However, he is slain in a sword duel by Sinbad, who then takes the "crown of untold riches" that rises out of the fountain and gives it to the Grand Vizier. Sinbad explains to Margiana that he values freedom more, and a king is never really free. The crown's magic powers causes the Vizer's mask to dissolve to reveal his healed face, and Sinbad journeys back to Marabia with Haroun, who has proven himself during the adventure, as a new crew member and Margiana by his side.