Другую предал киноаппарат. Милая, славная в жизни, на экране она получилась значительно хуже. Очарование неправильных черт лица пропало, и осталась одна некрасивость. Трудно было поверить, что в такую Надю можно влюбиться в течение одной ночи, отвергнув при этом хорошенькую невесту, — получилась бы натяжка, авторский произвол.
Третья, которой я восхищался в драматических спектаклях, играла великолепно, но оказалась начисто лишенной юмора. Так, несмотря на несомненную одаренность всех претенденток, я постепенно понял, что просчитался — героини нет. А сроки съемок неумолимо приближались! Я зашел в тупик, не понимал, что же мне предпринять…»
Спасение, как всегда, пришло совершенно неожиданно. Однажды Рязанов вспомнил очень популярную в Советском Союзе польскую мелодраму «Анатомия любви» (1972), где главную женскую роль играла актриса Барбара Брыльска. И хотя актриса была Рязанову совершенно незнакома, но он раздобыл ее домашний телефон и позвонил ей в Варшаву. На удачу, она в тот момент оказалась совершенно свободной от съемок и согласилась прочитать сценарий, который Рязанов ей тут же и отправил. В итоге роль Нади ей понравилась, и Брыльска дала «добро» на съемки. Ее вызвали в Москву и устроили ей кинопробу точно на таких же условиях, как и всем советским актрисам, пробовавшимся до этого на эту роль. Как пишет сам Рязанов, «ее версия роли оказалась самой убедительной, и мы ее утвердили».
Тогда же был найден и актер на роль Жени Лукашина. В этом случае помогла ассистентка режиссера Наталья Коренева (супруга Алексея Коренева), которая после того как не подошли ни Петр Вельяминов, ни Станислав Любшин (последний ушел сам, обидевшись на предложение режиссера устроить конкурс между исполнителями, кто лучше сыграет), посоветовала Рязанову посмотреть актера театра «Современник» Андрея Мягкова, с которым давно дружила. Рязанов знал Мягкова как хорошего драматического актера, но в его комедийные возможности не очень-то верил. Поэтому к предложению снять кинопробу Мягкова отнесся скептически. Но, едва актер встал напротив камеры, сразу стало ясно, что именно он — основной кандидат на роль Лукашина. А после кинопробы съемочная группа единодушно его утвердила.
На роль Гали, на которую тоже пробовалось много молодых актрис (например, Наталья Гвоздикова, только что прогремевшая роль Полины в «Большой перемене»), была утверждена актриса Театра имени Гоголя Ольга Науменко. Роль Ипполита досталась актеру ленинградского БДТ Олегу Басилашвили.
Большое место в фильме должна была играть музыка, которую написал Микаэл Таривердиев. Он же отыскал и исполнителей, которые должны были спеть песни за героев Андрея Мягкова и Барбары Брыльской. Это были Сергей Никитин и Алла Пугачева. С последней Таривердиев был знаком еще по работе над фильмом «Король-Олень», однако потом он потерял ее из виду и, приступая к «Иронии судьбы», даже в мыслях не имел ее в виду. Но затем… Впрочем, послушаем рассказ самого М. Таривердиева:
«Когда начались съемки «Иронии судьбы», мы стали искать певицу. Я пробовал очень многих. Была такая прелестная певица Валя Пономарева — она пробовалась, еще кто-то. Это было хорошо, но все же не подходило. Тогда я попросил Раису Александровну Лукину, замечательного музыкального редактора, просто легендарного редактора, найти Пугачеву. А Алла как-то после «Короля-Оленя» совершенно пропала. И где она? А бог знает где. Все же нашли ее. Начали мы с ней работать. Работали много, около месяца. Хотя, казалось бы, поет всего четыре романса. Вообще, конечно, ей трудно с нами было. Эльдар требует от нее одного, я — другого. Совсем замучили ее. На каждую песню было сделано по тридцать дублей. За целый день писали по одному романсу. В итоге она записалась замечательно. Эти ее записи не подвержены ни времени, ни моде, ни каким-то другим проходящим вещам. Эти записи уже остались. Записи, которые она делала потом, эстрадные, они оказались подверженными моде, от них уставали, их переставали слушать. А эти остались. И лучше нее никто после этого не спел…».
Съемки фильма должны были начаться 13 января 1975 года. Предстояло снимать зимние эпизоды, однако из-за установившейся в Москве теплой погоды сделать это удалось не сразу, а спустя несколько дней. А пока 14 января в Москву из Варшавы прилетела исполнительница главной женской роли — Надя Шевелева — Барбара Брыльска, чтобы примерить костюмы и проверить грим.
Вечером 18 января съемочной площадкой фильма стал столичный аэропорт Внуково, где снимался эпизод проводов Жени Лукашина в Ленинград. Как мы помним, отправился он туда не по собственной инициативе, а по воле двух своих подвыпивших дружков, которых в фильме играли Георгий Бурков и Александр Белявский. Последний вспоминает: