Сложнее всего проходили поиски героини. Леонид Гайдай любил снимать уже проверенных артистов, но на самую главную роль зачастую выбирал того, с кем ранее не работал. Иногда таковым оказывался никому не известный актер, который после съемок у Гайдая в буквальном смысле просыпался знаменитым. Так позже случится с Арчилом Гомиашвили, который сыграет главную роль в «12 стульях». И в точно такой же ситуации оказалась Наталья Барлей, попав в «Кавказскую пленницу».

Изначально на роль Нины (героиня была названа в честь Нины Гребешковой) пробовались сплошные «звезды» — сестры Марианна и Анастасия Вертинские, Жанна Болотова, Лариса Голубкина, Виктория Федорова, Валентина Малявина, Раиса Недашковская, Наталья Фатеева, Наталья Кустинская. Пробовал Гайдай и полюбившуюся ему Наталью Селезневу, но эта кандидатура была, пожалуй, самой неподходящей — зрители стали бы путать студентку Лиду из «Операции «Ы»…» и студентку Нину из «Кавказской пленницы».

По мере просмотра десятков актрис Гайдай всё больше склонялся к кандидатуре Натальи Кустинской. Однако она предпочла принять предложение Владимира Мотыля, в это же время собиравшегося снимать на «Ленфильме» «Женю, Женечку и «катюшу». (В конце концов Кустинская неожиданно попала в больницу и не снялась ни у Мотыля, ни у Гайдая.)

Тогда-то на съемочной площадке и возникла восемнадцатилетняя цирковая эквилибристка Наталья Барлей. Знакомством с ней Гайдай обязан режиссеру Одесской киностудии Георгию Юнгвальд-Хилькевичу. Вот что рассказал по этому поводу сам Хилькевич в своей книге воспоминаний:

«К тому времени я уже начал снимать свою дипломную работу — фильм «Формула радуги».

Мне нужна была молодая девчонка на маленький эпизод. А у нас в стране молодых звезд фактически нет. Пока актриса окончит ВГИК, она уже — молодая дама…

Из Москвы в Одессу приехал цирк. А я всегда был страстным любителем этого зрелища. И конечно, пошел на представление. На проволоке с веерами танцевала изумительной красоты девушка. Я был потрясен ее необыкновенной внешностью.

У нее были огромные ласковые глаза. Очень трудно встретить в нашей стране женщину с ласковыми глазами. У всех глаза озлобленные, озабоченные, с каким-то напряженным выражением. У Наташи были сияющие глаза, белые зубы, словно выточенный носик и персиковый цвет кожи. Очень длинные прямые ресницы и красивые губы, которые всем хотелось поцеловать… А волосы — такие льющиеся, блестящие, ну просто созданные для рекламы! Ни у одной советской женщины я не видел таких тяжелых и ухоженных волос. В Наташе было столько обаяния, естественности, что я был сражен. В тот момент, когда я увидел Варлей, я понял, что эта внешность создана для кинематографа.

Конечно, я тут же стал пробовать ее на главную роль. Мы ее старили, одевали и так, и эдак, делали разные гримы, прически… Но выглядела она лет на пятнадцать, не больше. И на главную роль ну никак не подходила. Сыграла всего лишь крохотный эпизод — медсестру, — который стал трамплином к ее киноуспеху.

Дербенев и Зацепин в это время писали мне песни, а параллельно у них шла работа с Гайдаем. Как раз начиналась подготовка к съемкам «Кавказской пленницы» Как-то я поделился с ними своими восторгами по поводу канатоходки. А они тут же рассказали о ней Гайдаю. Он прислал в Одессу ассистентку, та увидела Варлей, и судьба Наташи была решена. Потом ее вызвали на пробы и действительно утвердили на роль в «Кавказской пленнице», откуда и пошла ее слава.

— Не забудьте поставить мне коньяк, — предупредил я съемочную группу «Пленницы». Мне с радостью пообещали. И точно, через какое-то время коньяк был мне доставлен из Москвы.

Вот так и началась актерская карьера Варлей».

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

Разумеется, приведенный фрагмент писался еще тогда, когда авторы и понятия не имели о существовании юной Варлей. Сегодня немыслимо представить себе на ее месте какую-либо другую актрису (а уж Кустинскую — совсем невозможно). Конечно, особенными актерскими способностями Варлей на тот момент похвастаться не могла, но всё искупали ее огромное обаяние и, как правильно заметил Юнгвальд-Хилькевич, сам возраст Натальи. 25—30-летние женщины (а таковыми были почти все остальные претендентки) мало подходили на эту роль.

«Наталья Варлей ничего не умела делать в кино, — вспоминал позже Гайдай, — но был в ней природный артистизм, которому подвластно многое. Кроме того, она отлично выполняла все трюки, а их немало в картине».

Понравилось Леониду Иовичу и то, что Наталья запросто согласилась сниматься в купальнике, который был фактически ее рабочей формой в цирке. Гайдай второй раз подряд «раздевал» своих героинь на экране. А когда режиссера спрашивали, так ли уж это необходимо, он неизменно отвечал: «Брижит Бардо в купальнике выглядит талантливее, чем Фаина Раневская».

Снимать «Кавказскую пленницу» начали 22 апреля 1966 года в Москве. На этот раз павильонные съемки предшествовали натурным (экспедицию в Крым отложили на лето). Последним съемочным днем на «Мосфильме» было 19 мая. В этот день там побывала корреспондентка журнала «Советский экран» Н. Орлова. Ее репортаж приоткрывает еще одну завесу над тем, как Гайдай работал с актерами:

«Смена началась в 16.30 и должна была закончиться в 24.00. Снимали последние кадры в павильоне перед выездом на «натуру» Впереди группу ждали Крым и Кавказ, а сегодня «юг» сконцентрировался в девятом павильоне «Мосфильма» и напоминал о себе только зеленым тряпочным плющом, лихо приколотым декораторами к белой стене, да стайкой «южных курортниц» — актрис массовки.

Снимали сорок девятый кадр — сцену в ресторане. В нем был занят только один актер — Александр Демьяненко… Шурика знакомят в ресторане с местными тостами и потчуют молодым вином. Это уже далеко не первый тост, но зато самый трогательный для Шурика — про птичку… Шурик неожиданно всхлипывает.

— Что такое, дорогой? — спрашивают его.

— Птичку жалко! — и разражается бурными детскими слезами.

Идет репетиция. Рядом с Шуриком — Демьяненко — режиссер-постановщик Леонид Гайдай. Вместе с актером он сотрясается в рыданиях.

— Птичку жалко… Вот так. Хорошо. Давайте снимать.

— Кадр 49, дубль 1, — сказал ассистент. Отсняли семь метров.

— А теперь, Саша, попробуй так, — говорит режиссер. — Ты страшно огорчен, но ты мужчина, ты держишь себя в руках, ты полон достоинства. «Птичку жалко!» И, сжав зубы, скупо, по-мужски плачешь.

Перед пятым дублем у Саши Демьяненко высохли слезы, пришлось сделать глицериновые. Припудрили нос. Снова съемка… Растрепанный парень в вылинявшей ковбойке наконец плачет вполне удовлетворительно. Дубль удался.