Таким же мучительным оказался и поиск исполнительницы на роль Нади Шевелевой. После того как отпала кандидатура Людмилы Гурченко, эту роль примеряли на себе многие известные актрисы: Светлана Немоляева, Галина Шуранова и др. Как вспоминает Э. Рязанов:

«Кинопробы сменяли одна другую, и постепенно выяснилось, что идеальной претендентки нет. Все актрисы работали превосходно, точно, талантливо. Но помимо дарования существуют еще психофизические данные. Личные качества актрис в каких-то важных гранях не совпадали со свойствами героини. Одна при поразительной нюансировке чувств была несколько вульгарна, и сюжет сразу же получал иной крен. Ни о каких возвышенных материях и зарождении высокой любви не могло быть и речи. Скорее получилась бы история об однодневной интрижке.

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

Третья, которой я восхищался в драматических спектаклях, играла великолепно, но оказалась начисто лишенной юмора. Так, несмотря на несомненную одаренность всех претенденток, я постепенно понял, что просчитался — героини нет. А сроки съемок неумолимо приближались! Я зашел в тупик, не понимал, что же мне предпринять…»

Спасение, как всегда, пришло совершенно неожиданно. Однажды Рязанов вспомнил очень популярную в Советском Союзе польскую мелодраму «Анатомия любви» (1972), где главную женскую роль играла актриса Барбара Брыльска. И хотя актриса была Рязанову совершенно незнакома, но он раздобыл ее домашний телефон и позвонил ей в Варшаву. На удачу, она в тот момент оказалась совершенно свободной от съемок и согласилась прочитать сценарий, который Рязанов ей тут же и отправил. В итоге роль Нади ей понравилась, и Брыльска дала «добро» на съемки. Ее вызвали в Москву и устроили ей кинопробу точно на таких же условиях, как и всем советским актрисам, пробовавшимся до этого на эту роль. Как пишет сам Рязанов, «ее версия роли оказалась самой убедительной, и мы ее утвердили».

Тогда же был найден и актер на роль Жени Лукашина. В этом случае помогла ассистентка режиссера Наталья Коренева (супруга Алексея Коренева), которая после того как не подошли ни Петр Вельяминов, ни Станислав Любшин (последний ушел сам, обидевшись на предложение режиссера устроить конкурс между исполнителями, кто лучше сыграет), посоветовала Рязанову посмотреть актера театра «Современник» Андрея Мягкова, с которым давно дружила. Рязанов знал Мягкова как хорошего драматического актера, но в его комедийные возможности не очень-то верил. Поэтому к предложению снять кинопробу Мягкова отнесся скептически. Но, едва актер встал напротив камеры, сразу стало ясно, что именно он — основной кандидат на роль Лукашина. А после кинопробы съемочная группа единодушно его утвердила.