Фильм снят по мотивам романа Нила Геймана «Звездная пыль» (Stardust, 1998).

Сара Мишель Геллар отказалась от предложенной ей главной женской роли для того, чтобы иметь возможность проводить больше времени со своим мужем Фредди Принцем мл.

Алекс Петтифер пробовался на роль Тристана Торна.

Последний фильм известного британского актёра Марка Бёрнса, сыгравшего роль епископа. Он скончался 8 мая 2007 года, за три месяца до премьеры «Звёздной пыли».

Права на экранизацию сказочной новеллы Нила Геймана первоначально приобрела студия Miramax Films ещё осенью 1998 года. В течение некоторого времени проект находился в стадии разработки, но никаких реальных шагов предпринято не было, и после истечения срока действия прав они вновь вернулись к автору.

В качестве двух основных претендентов на режиссёрское кресло в течение долгого времени выступали Терри Гиллиам и Мэттью Вон. Первый из них отказался от поступившего предложения, поскольку только что перед этим завершил съёмки «Братьев Гримм» (2005) и не хотел связывать себя ещё с одним сказочным проектом. Мэттью Вон в это время был занят работой над британской картиной «Слоёный торт» (2004), а позднее должен был приступить к съёмкам кинокомикса «Люди Икс: Последняя битва» (2006).

Вскоре после того как Мэттью Вон неожиданно для всех выбыл из работы над «Последней битвой», переговоры между ним и Нилом Гейманом возобновились, в результате которых автор предоставил права на будущую экранизацию абсолютно бесплатно. Такое решение писателя во многом было основано на том, что он доверял Мэттью Вону не только как другу, но и как человеку, который всегда держит своё слово, что, по мнению Геймана, является большой редкостью в Голливуде.

После предварительного обсуждения будущей картины с Мэттью Воном Нил Гейман посчитал, что режиссёр отлично справится с постановкой приключенческих и экшен сцен, но нуждается в помощи с романтической стороной истории. Для того, чтобы дополнить его стиль и лучше передать все аспекты сказочной новеллы, Нил Гейман познакомил Мэттью Вона со сценаристом Джейн Голдман, и они вдвоём взялись за работу над сценарием.

В фильме каждая из трёх ведьм имеет своё имя, тогда как в книге они называются общим именем Лилим и не имеют собственных имён. Их зовут Ламия, Морфо и Эмпуза в честь кровожадных демонических существ из греческой мифологии.

В книге Нила Геймана главного героя зовут Тристран, но в фильме буква «р» в середине была удалена, что дало в результате более знакомое и привычное нам Тристан. Это было сделано главным образом для удобства произношения.

Роль Ферди, торговца, который покупает молнии у капитана Шекспира, могла достаться Винни Джонсу.

Съёмки фильма прошли с 19 апреля по 13 июля 2006 года на лондонской студии Pinewood Studios, а также в различных уголках Англии, Шотландии и Уэльса. Кроме этого несколько сцен было отснято в Исландии, в окрестностях городка Хабнарфьордюр.

У всех принцев можно заметить на одежде узор, отображающий их номер по старшинству римскими цифрами, составленный из более мелких арабских цифр. Кроме этого Септимус носит камзол с цифрой 7 на каждой пуговице.

Имена принцев (Праймус, Секундус и т. д.) — римские имена, означающие Первый, Второй, Третий… Имя принцессы Уны в переводе с итальянского значит «Единственная».

Корабль капитана Шекспира носит название «Каспартина» в честь детей режиссера Мэтью Вона — Каспара и Клементины. Такое же название носит подводная лодка в другом фильме Мэтью Вона — Люди Икс: Первый Класс.

Имена главных героев Тристан и Ивэйн взяты у персонажей средневекового эпоса о короле Артуре и рыцарях Круглого стола.

Марк Стронг, исполнивший роль Септимуса, ранее сыграл главную роль в сериале «Подснежник» (The Long Firm), где его герой владел ночным клубом под названием «Stardust» ("Звездная пыль").

На 63 мин. фильма Мишель Пфайффер в зеркале выглядит молодой, хотя должна выглядеть уже старой, как на минуту ранее, поскольку потеряла уже свою энергию.