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