Поскольку Юрий Никулин и в этот раз отбыл на длительные зарубежные гастроли, его кандидатура на роль Деточкина даже не рассматривалась. Занят был и Леонид Быков. Поэтому на роль современного Робин Гуда Рязанов стал пробовать самых разных артистов: Василия Ланового, Михаила Державина (пробы 19, 22–23 апреля), Леонида Куравлева (5 и 7 мая), Александра Белявского, Иннокентия Смоктуновского (14–15 мая). Из всех перечисленных кандидатур больше всего Рязанова устраивал Смоктуновский, которого он предполагал пригласить на эту роль еще два года назад, но тогда он снимался в «Гамлете». Однако Смоктуновский и в этот раз оказался занят: он играл самого Ленина в фильме «На одной планете». Тогда Рязанов предпринял отчаянные меры, чтобы уговорить актера сниматься и у него. Собрав небольшую съемочную группу, он отправился в Ленинград, чтобы там снять последние кинопробы Смоктуновского. Они состоялись 20421 мая (в роли следователя Максима Подберезовикова Смоктуновскому подыгрывал Олег Борисов). Несмотря на то, что проба получилась не слишком удачная (сказалась усталость Смоктуновского), он дал свое окончательное «да» на участие в фильме.
31 мая прошли пробы еще трех актеров, которых Рязанов тоже взял в картину: Анатолия Папанова (Сокол-Кружкин), Андрея Миронова (Дима Семицветов) и Татьяны Гавриловой (Инна Семицветова). 7 июня состоялось утверждение перечисленных актеров худсоветом.
Между тем именно в эти дни из Ленинграда от Смоктуновского пришла убийственная телеграмма следующего содержания: «К сожалению, сниматься не могу, врачи настаивают длительном отдыхе. Пожалуйста, сохраните желание работать вместе другом фильме, будущем. Желаю успеха, уважением Смоктуновский». Это был удар, которого в группе никто не ожидал. У кого-то даже возникла благородная мысль: раз Смоктуновский не может участвовать в картине, отказаться от фильма, не снимать. По этому поводу даже был собран костяк группы (Рязанов, операторы-постановщики Владимир Нахабцев и Анатолий Мукасей, художник Борис Немечек, второй режиссер Алексей Коренев, художник по костюмам Быховская), который пытался вместе решить эту дилемму: снимать или не снимать? Рязанов предложил проголосовать. Все участники собрания подняли руки за то, чтобы снимать. И группа стала искать другого исполнителя.
Была проведены пробы с несколькими актерами, в том числе и с Олегом Ефремовым, который буквально загорелся ролью Деточкина. Но он не подошел по типажу. Увидев его на экране в этой роли, художник фильма Немечек сказал: «Это же волк в овечьей шкуре!» Все немедленно с ним согласились: сквозь мягкость, добросердечие и наивность в Ефремове проглядывал волевой и железный человек. Но чтобы не обижать актера, ему была предложена без всякой кинопробы роль следователя Подберезовикова. Ефремов предложение принял.
В итоге к концу июня были подобраны исполнители практически на всех главных героев. Мать Деточкина должна была играть Любовь Добржанская; его возлюбленную Любу — Ольга Аросева; Максима Подберезовикова — Олег Ефремов; Диму Семицветова — Андрей Миронов; его жену Инну — Татьяна Гаврилова; Сокол-Кружкина — Анатолий Папанов; инспектора ОРУДа — Георгий Жженов; режиссера самодеятельного театра — Евгений Евстигнеев; начальника Деточкина — Георгий Ронинсон; директора пивной — Сергей Кулагин; католического священника — Донатас Банионис и др. Короче, найдены были все, кроме главного героя — Юрия Деточкина. Понимая, что дальнейшее промедление грозит срыву съемок, Рязанов решил вновь обратиться за помощью к Иннокентию Смоктуновскому. Сначала он послал к нему его близкого друга Георгия Жженова (они были знакомы с 46-го года), а когда тот вернулся не солоно хлебавши, решил отправиться к актеру сам.
28 июня Рязанов примчался на «Красной стреле» в Ленинград. Погода в тот день была мерзопакостная: когда режиссер вышел на площадь перед Московским вокзалом, лил проливной дождь. Рязанов позвонил Смоктуновскому домой, но телефон молчал. Тогда Рязанов отправился на «Ленфильм», думая, что актер находится на съемках фильма «На одной планете». Но там ему сообщили, что Смоктуновский болен и живет на даче, в ста километрах от города. К счастью, покидая Москву, Рязанов запасся рисунком-планом, как проехать на дачу актера, которым его снабдил Георгий Жженов. Благодаря этому рисунку режиссер разыскал нужную дачу: она располагалась в поселке Горьковской, в 11 километрах от шоссейной дороги. Далее послушаем рассказ самого И. Смоктуновского:
«Сквозь сон я услышал легкий шепот сына Филиппа: «Папа, вставай, дядя приехал». Чувствовал я себя из рук вон плохо, с трудом открыл глаза и онемел от увиденного. Режиссер стоял в проеме двери, весь в черном, с него стекала вода и почему-то шел пар. Он очень хорошо и просто-просто улыбался (это он решил делать, еще «подплывая» к даче). А реальность своего появления и вообще бытия он усугубил фразочкой тоже простой-простой: «Здравствуйте, Кеша!» Так, надо полагать, в далекой древности появлялись и обращались к народу святые.