Рабочее название фильма — «Запах камня» — в процессе съемок было заменено на «Изгнание», которое, по мнению авторов, наиболее точно выражает философскую концепцию фильма.

Когда было решено пригласить на пробы актрису Шведского королевского театра Марию Бонневи, возникла сложность: по контракту с театром Мария должна была ближайший год играть в новом спектакле, премьера которого уже была анонсирована. «Когда мы стали искать способ, как сделать так, чтобы Мария смогла участвовать в съемках, мне сказали: этот вопрос тебе придется решать с премьер-министром», — вспоминает продюсер Дмитрий Лесневский. По шведским законам спектакль не может быть отменен, если на него продан хотя бы один билет. Лесневский предложил директору театра выкупить билеты на все спектакли с участием Марии Бонневи. Но, к сожалению, хотя до премьеры оставалось еще несколько месяцев, 5 билетов было уже продано. И все же решение было найдено: чтобы дождаться Марию, съемки фильма пришлось перенести почти на год.

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

При озвучивании текст Веры (героини Марии Бонневи) был продублирован Еленой Лядовой. Поиски актрисы для дубляжа шли несколько месяцев, параллельно с монтажом картины. Было прослушано более семидесяти кандидатур. Чтобы не быть предвзятым, режиссер решил, что все они инкогнито для него озвучат по две ключевые сцены. После чего он прослушал записи, и выбрал для последнего этапа проб несколько голосов. Окончательный выбор пал на Елену: ее голос, по мнению режиссера, идеально подходит к тому образу, что создает Мария Бонневи в роли Веры.

Съемки фильма проходили в нескольких странах – во Франции и Бельгии, где снимались городские экстерьеры, в России, в Москве – павильонные, интерьерные съемки, а также в Молдове, где специально для съемок был построен дом, мост через овраг, церковь, а также кладбище рядом с церковью. Особенно сложно оказалось спроектировать церковь и кладбище – они не должны были содержать очевидных признаков принадлежности какой-то определенной конфессии. Церковь, как и дом на холме, в кадре должны были выглядеть очень старыми, что подразумевало тщательную работу декораторов с фактурами. Для этой задачи в команду художников были приглашены немецкие специалисты, которые с помощью современных технологий сумели сделать «качественный замшелый камень» и «состарить» дерево.

Одна треть пленки, затраченной на съемки фильма «Изгнание», а именно – 20 000 метров Кодака, была подарена Луиджи де Лаурентисом в Венеции, в 2003 году, в качестве приза за лучший режиссерский дебют («Возвращение»). Вторая треть тоже явилась премией за фильм «Возвращение». Сертификат на 17 000 метров негативной пленки Кодак вручила Академия Ника за лучший российский фильм 2004 года.