Л. Гайдай: «У меня трудное положение. Я не знаю материала, на котором написан сценарий, поэтому ни о чем не могу судить с уверенностью. Так сложились обстоятельства, что в работе над первым вариантом я участия не принимал (как мы помним, Гайдай думал совсем про другую картину. — Ф. Р.), а подключился только в последние месяцы. Второй вариант мне нравится значительно больше, чем первый… Я считаю, что надо поехать на материал, посмотреть, как живут там люди, каковы они…»

Далее Гайдай делает сенсационное заявление: «Троицы не будет. Никулин сниматься отказался…»

Юрий Никулин действительно, прочитав сценарий, сниматься в картине отказался. Как написал он сам в своих мемуарах: «Я скептически отнесся к сценарию картины и, сознаюсь, в успех ее не верил. Многое в сценарии мне казалось нарочитым…» Однако спустя два месяца Гайдай внезапно изменил свое решение: он решил задействовать троицу в будущем фильме и сумел уговорить Никулина сниматься.

21 января 1966 года фильм «Кавказская пленница» был запущен в подготовительный период.

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

25 января Гайдай, Бровин и директор картины Фрейдин выехали на Кавказ, чтобы выбрать места для натурных съемок. С 1 февраля начались фотопробы актеров на главные и эпизодические роли. 16 февраля все та же сценарно-редакционная коллегия обсудила окончательный вариант сценария и одобрила его. По договору, заключенному со сценаристами, им обязались выплатить 8 тысяч рублей, из которых Слободскому и Костюковскому причиталось по 3 тысячи рублей, Гайдаю — 2 тысячи.

20 февраля Гайдай, Бровин и еще несколько человек из съемочной группы выехали в Крым, чтобы выбрать места натурных съемок уже там (Кавказ не подошел).

10 марта в павильоне № 13 «Мосфильма» начались кинопробы актеров. В тот день там пробовались: Александр Демьяненко (Шурик), Владимир Этуш (Саахов), Михаил Глузский (администратор гостиницы). 11 марта в другом павильоне — № 12–пробовались: Демьяненко, Раутбарт, Попов.

15 марта — пробы: Демьяненко, Анастасия Вертинская, Наталья Селезнева (обе актрисы пробовались на роль Нины).

16 марта — пробы: Демьяненко, Фрунзик Мкртчян (Джабраил).

17 марта — пробы: Спартак Мишулин, Перов.

18 марта — пробы: Демьяненко, Раиса Недашковская, Жанна Болотова (обе актрисы пробовались на роль Нины).

С 24 марта по 5 апреля из-за болезни Гайдая пробы не проводились.

5 апреля — пробы: Герман Качин, Лариса Голубкина (на Нину).

7 апреля — пробы: Наталья Величко, Корнева (на Нину).

Как нашли Нину

К этому моменту актерский ансамбль в большинстве своем уже сложился. Были утверждены: Александр Демьяненко (Шурик), Владимир Этуш (Саахов), Юрий Никулин (Балбес), Георгий Вицин (Трус), Евгений Моргунов (Бывалый), Фрунзик Мкртчян (Джабраил), Руслан Ахметов (Эдик), Михаил Глузский (администратор), Нина Гребешкова (врач) и др. Однако на роль красавицы Нины никто из просмотренных кандидаток (а их перед его взором вживую и на фотографиях прошло около пяти сотен) Гайдаю не приглянулись. Помог случай в лице ассистентки Гайдая, которая случайно оказалась в Одессе на съемках фильма «Формула радуги», который снимал Георгий Юнгвальд-Хилькевич. Она и обратила внимание на совсем молодую актрису Наталью Варлей, игравшую в фильме медсестру.