This movie is inspired by the Bulgarian movie Yo ho ho (1981).
The film was shot on 26 locations over 18 countries.
The director claims that there are no special effects in the film despite its surreal looks. Everything was shot on real locations.
A miscommunication between the casting agent and Catinca Untaru led her to believe that Lee Pace was a real-life paraplegic. Director Tarsem Singh found that this brought an added level of believability to their dialogue, so he decided to keep almost the entire cast and crew under the same impression. Singh had to speak to the actor playing Alexandria's father and explain that his role was smaller than it appeared, since the script implied that he played the role of the bandit (actually played by Pace) in the fantasy scenes. Apparently it was hard to keep up the lie - a makeup artist walked into a room to find Pace standing and almost passed out from shock.
Catinca Untaru didn't speak English. She learned the lines by heart.
The horses used by the Bandit and his crew in many scenes are of the Marwari breed, native only to the deserts of India, and known for their distinctive "lyre or scimitar"-shaped ears.