Далее Гайдай делает сенсационное заявление:
"Троицы не будет. Никулин сниматься отказался…"
Юрий Никулин действительно, прочитав сценарий, сниматься в картине отказался. Как написал он сам в своих мемуарах: "Я скептически отнесся к сценарию картины и, сознаюсь, в успех ее не верил. Многое в сценарии мне казалось нарочитым…" Однако спустя два месяца Гайдай внезапно изменил свое решение: он решил задействовать троицу в будущем фильме и сумел уговорить Никулина сниматься.
21 января 1966 года фильм "Кавказская пленница" был запущен в подготовительный период.
В качестве своих соавторов Гайдай взял в картину следующих людей: оператор Константин Бровин, композитор Александр Зацепин — уже работавшие с Гайдаем кадры; художник-постановщик В. Каплуновский, звукооператор В. Крачковский (кстати, супруг Натальи Крачковской, которая вскоре станет одной из любимых актрис Гайдая) — новые люди.
25 января Гайдай, Бровин и директор картины Фрейдин выехали на Кавказ, чтобы выбрать места для натурных съемок. С 1 февраля начались фотопробы актеров на главные и эпизодические роли. 16 февраля все та же сценарно-редакционная коллегия обсудила окончательный вариант сценария и одобрила его. По договору, заключенному со сценаристами, им обязались выплатить 8 тысяч рублей, из которых Слободскому и Костюковскому причиталось по 3 тысячи рублей, Гайдаю — 2 тысячи.
20 февраля Гайдай, Бровин и еще несколько человек из съемочной группы выехали в Крым, чтобы выбрать места натурных съемок уже там (Кавказ не подошел).
10 марта в павильоне № 13 «Мосфильма» начались кинопробы актеров. В тот день там пробовались: Александр Демьяненко (Шурик), Владимир Этуш (Саахов), Михаил Глузский (администратор гостиницы). 11 марта в другом павильоне — № 12 — пробовались: Демьяненко, Раутбарт, Попов.
15 марта — пробы: Демьяненко, Анастасия Вертинская, Наталья Селезнева (обе актрисы пробовались на роль Нины).
16 марта — пробы: Демьяненко, Фрунзик Мкртчян (Джабраил).
17 марта — пробы: Спартак Мишулин, Перов.
18 марта — пробы: Демьяненко, Раиса Недашковская, Жанна Болотова (обе актрисы пробовались на роль Нины).
С 24 марта по 5 апреля из-за болезни Гайдая пробы не проводились.
5 апреля — пробы: Герман Качин, Лариса Голубкина (на Нину).
7 апреля — пробы: Наталья Величко, Корнева (на Нину).
К этому моменту актерский ансамбль в большинстве своем уже сложился. Были утверждены: Александр Демьяненко (Шурик), Владимир Этуш (Саахов), Юрий Никулин (Балбес), Георгий Вицин (Трус), Евгений Моргунов (Бывалый), Фрунзик Мкртчян (Джабраил), Руслан Ахметов (Эдик), Михаил Глузский (администратор), Нина Гребешкова (врач) и др. Однако на роль красавицы Нины никто из просмотренных кандидаток (а их перед его взором вживую и на фотографиях прошло около пяти сотен) Гайдаю не приглянулись. Помог случай в лице ассистентки Гайдая, которая случайно оказалась в Одессе на съемках фильма "Формула радуги", который снимал Георгий Юнгвальд-Хилькевич. Она и обратила внимание на совсем молодую актрису Наталью Варлей, игравшую в фильме медсестру.