Фильм "Операция «Ы» еще не вышел в прокат, а оба его сценариста Морис Слободской и Яков Костюковский — уже засели за сочинение новых приключений Шурика. Естественно, режиссером картины они видели только Леонида Гайдая, однако тот думал несколько иначе. Сняв "Операцию «Ы», он считал, что этот фильм опустошил его как режиссера, что Шурик уже себя исчерпал, да и троица тоже. Поэтому ему хотелось снимать иное кино, тоже комедию, но уже с другими персонажами. Но руководство «Мосфильма», видя, какой триумф обрушился на "Операцию «Ы», чуть ли не в приказном порядке заставило Гайдая взяться за продолжение фильма.

15 июня 1965 года заявка сценаристов на новую комедию поступила в творческое объединение «Луч» при киностудии «Мосфильм» (бывшее 2-е объединение) и была принята. Будущий сценарий носил название "Шурик в горах" и состоял из двух новелл. В первой — "Кавказская пленница" — речь шла о том, как красивая девушка Нина приехала на каникулы к своим родственникам на Кавказ, но была похищена местным сластолюбивым «князьком» Ахоховым. Но Шурик вызволяет девушку из рук похитителя.

Во второй новелле — "Снежный человек и другие" — сюжет был таков: научная экспедиция под руководством видного ученого (роль писалась специально под Михаила Пуговкина, несмотря на то, что худрук «Луча» Пырьев был против этой кандидатуры) ищет в горах снежного человека. Ей удается выйти на его след, но поймать не получается. Но группа даже не догадывается, что за снежного человека себя выдает — троица в лице Труса, Балбеса и Бывалого. После того как провалилась их затея с похищением Нины, они сбежали в горы и стали выдавать себя за "снежного человека", чтобы сбить со следа милицию. Однако Шурик и Нина разоблачают авантюристов.

26 октября сценарно-редакционная коллегия вновь собралась на свое заседание, чтобы обсудить сценарий под названием "Шурик в горах". На этот раз он представлял из себя сценарий полнометражного фильма (новелл в нем уже не было), сюжет которого вращался вокруг похищения девушки. Приведу отрывки из некоторых выступлений участников того заседания:

Л. Арнштам (режиссер): "Сценарий тяжелит во многом троица. Она требует для себя отдельных интермедий. Но троица работает уже на отработанном материале. Она изжила себя. Эти маски себя исчерпали, так как они примитивны…"

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

Далее Гайдай делает сенсационное заявление:

"Троицы не будет. Никулин сниматься отказался…"

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

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 году, сочинили для нас танец под названием "Копейка рубль бережет". Мы с фанерными огромными копейками по бокам выбегали на арену и радостно выкрикивали: "Копейка!", а последняя десятая «копейка» кричала: "Гривенник!" И вот в очередной раз, выбегая в победном марше несокрушимой копейки, я застряла между зрителями. «Копейки» рассчитались без меня, и гривенник получился из девяти копеек. Все очень смеялись. Кстати, на представлениях я встречалась с Юрием Никулиным…"