Закончив сценарий, Рязанов не спешил обращаться непосредственно к Путину, благодаря которому, собственно, и затеял весь проект. Первоначальная небольшая сумма денег на съемки «Андерсена» была выделена Федеральным агентством по культуре и кинематографии.

Начался подготовительный период — пошив костюмов, строительство декораций, экспедиция в Данию для выбора мест натурных съемок… И, разумеется, кинопробы.

Наибольшую трудность представлял поиск исполнителя главной роли. Смоктуновский умер еще в 1994-м — в 2005-м уже не было такого актера, в котором Рязанов «дистанционно» мог разглядеть Андерсена. Изначально было понятно, что подбирать нужно двух артистов — на юного и на зрелого Ханса Кристиана. Режиссер решил сначала найти опытного возрастного исполнителя, а потом уже искать его молодого «двойника» среди начинающих.

Была мысль: пригласить в картину американца Эдриена Броди, понравившегося Рязанову в фильме Романа Поланского «Пианист» (2002), — но, кажется, никаких действий в этом направлении Эльдар Александрович все же не предпринял.

Актера Санкт-Петербургского академического театра имени Ленсовета Сергея Мигицко, которому в 2005-м было 52 года, Рязанов пригласил попробоваться на одну из второстепенных ролей — Морица Мельхиора, еврея, в доме которого долгое время жил Ханс Кристиан. Но при первой же встрече с Мигицко режиссер обомлел. «Вылитый Андерсен!» — мелькнуло в его голове. И хотя энтузиазма Эльдара Александровича по поводу данного артиста больше никто из съемочной группы не разделял, решение было фактически принято.

Мигицко же подсказал, кого взять на роль молодого Андерсена. Актер знал, что в московском театре «Ленком» играет 23-летний Станислав Рядинский, весьма на него похожий. Так главными исполнителями в фильме Рязанова впервые за долгое время стали незвездные артисты.

Зато уж женские роли были отданы актрисам известным: безответно влюбленной в Андерсена горбатой Генриеттой стала Алена Бабенко, а шведской оперной дивой Йенни Линд, которую безответно любил сам Андерсен, — Евгения Крюкова, так восхитившая Рязанова на съемках «Ключа от спальни».

Из более давних любимиц режиссера в «Андерсене» сыграли лишь Наталья Щукина (балерина мадемуазель Шалль) и Лия Ахеджакова (совсем крошечная роль гадалки).

Небольшую, но сверхзначительную, обрамляющую повествование роль Господа Бога, притворившегося обитателем дурдома (или наоборот), исполнил Вячеслав Тихонов, почти ровесник режиссера. То было первое и последнее появление Вячеслава Васильевича в картине Эльдара Александровича, хотя знакомы они были со студенческой скамьи.