Alex Pettyfer auditioned for the role of Tristan Thorn.
Sarah Michelle Gellar turned down the lead role to spend more time with her husband.
Miramax originally had the option on ‘Stardust’, but after it expired, Neil Gaiman felt uncomfortable giving up the rights to the film to just anyone. After turning down numerous directors and young actresses who wanted it as a starring vehicle, Gaiman finally gave Stardust's option for free to Matthew Vaughn. This was largely due to the fact that Gaiman trusted Vaughn both as a friend and as someone "who stuck to his word," something Gaiman considered a rarity in Hollywood.
After initial conversations between Neil Gaiman and Matthew Vaughn about how to make the film, Gaiman found that Vaughn was most comfortable with all the action sequences and adventure bits but needed help with the romance side of the story. To complement Vaughn's style and better capture all the aspects of the book, Gaiman introduced him to writer Jane Goldman, and the two hit it off and wrote the screenplay.
Terry Gilliam was offered the job of directing the movie, but having just finished The Brothers Grimm (2005), wanted a break from fairy tales.
All princes wear clothing with a pattern spelling out their number in Roman numerals, composed by smaller Arabic numerals. Furthermore, Septimus wears a vest with the numeral 7 on each button.
The last film of Mark Burns who plays Bishop, he died before the film came out.
Release prints were delivered to theaters with the fake title 'Rusty'.
In some areas, release prints were delivered to theaters with the fake title 'Bright'
Author Neil Gaiman began writing the novel back in 1994.
The lead character's name was shortened from the book's Tristran, with a "r" between the "t" and "n", to Tristan because Tristran was hard to pronounce quickly. However there is one time it is said as "TristRan" instead of "Tristan". This is during the scene when Tristan remarks that Yvaine sometimes glows, when he suggests jokingly that the thing that Stars do best is to annoy boys called "TristRan Thorn".
The three witches share their names with demonic creatures from Greek mythology. Lamia and Mormo were demons who ate children, and Empusa was a creature sent by the goddess Hecate to eat travelers.
The Princes' names all refer back to their place in the family; Primus, the first born (Primary); Secundus, the second born; Tertius, the third (Tertiary) and so on in that fashion. Likewise, Una the Princess, is the first-born daughter (Un or Une means One in many countries).