Robert Shaw was a friend of producer Charles H. Schneer, who persuaded him to play the Oracle of All Knowledge in the film. Shaw agreed, as a favor, but requested that he not get any credit for the role. Shaw was extremely popular at the time, and felt that the genre was beneath him. His face was heavily swathed in make-up, and his voice electronically altered by a sound engineer. Shaw was paid £5,000 for just 20 minutes of work.
When Sinbad and the others land on Lemuria, a cliff along the left side of the beach is covered with carvings. According to an interview given by Ray Harryhausen, the cliff does not exist. The scene was shot on a popular beach in Spain, and the cliff was a matte painting added to hide all the spectators.
According to Ray Harryhausen's early concept art for the project (illustrated in charcoal pencil), the griffin, which fights the one-eyed centaur, was originally going to be a Neanderthal man. The "Neanderthal man" concept later became the Troglodyte in Sinbad and the Eye of the Tiger (1977).
This film helped Tom Baker get the role of the Fourth Doctor in Doctor Who (1963). Producer Barry Letts went to see it shortly after Baker was recommended for the role.