После успеха «Операции Ы» Леонид Гайдай задумал продолжение фильма в виде двух небольших новелл. Действие должно было происходить в более экзотической обстановке, и новую картину назвали «Шурик в горах». «Кавказская пленница» была первой из задуманных частей, а вторая должна была называться «Снежный человек и другие» - это был рассказ о том, как Трус, Балбес и Бывалый скрывались от советского правосудия, выдавая себя за Йети. 15 июня 1965 года заявку подали на «Мосфильм», но утвердили только первую новеллу, что привело к созданию полнометражного фильма.
Сложности начались, как только приступили к подбору актеров. Как ни странно, но первыми отказались сниматься в новом фильме Юрий Никулин и Евгений Моргунов. Им показалось, что комическая тройка слишком активно эксплуатируется, и это делает будущий фильм несколько односторонним. Никулин к тому же опасался, как бы роль Балбеса не оказалась слишком связана с ним. Кстати, именно это и произошло с Александром Демьяненко, оставшимся в памяти зрителей вечным Шуриком. Леонид Гайдай пошел на уступки знаменитым актерам, согласившись с их доводами. Сценарий был переработан.
Дальше начались поиски главной героини. По требованию режиссера, искали девушку, которая сразу бы привлекла к себе внимание зрителя. На роль Нины «примеряли» более 500 актрис! Список знаменитых на тот момент фамилий впечатляет: сёстры Вертинские, Жанна Болотова, Лариса Голубкина, Виктория Фёдорова, Валентина Малявина, Раиса Недашковская, Наталья Фатеева, Наталья Кустинская. Рассматривали кандидатуру и Натальи Селезневой, но Гайдай побоялся ассоциаций с предыдущими приключениями Шурика.
Судьба – сложный и запутанный клубок случайностей. Наталья Варлей работала гимнасткой в Московском цирке. Во время гастролей в Одессе ее на канате под куполом цирка заприметил Георгий Юнгвальд-Хилькевич (будущий режиссер «Д’Артаньяна и трех мушкетеров»). Он рассказал о красивой циркачке Леониду Гайдаю, и так на советском экране появился образ «студентки, комсомолки, спортсменки и просто красавицы» Нины. Гайдай вспоминал потом, что сначала «Она ничего не умела делать в кино, но был в ней природный артистизм, которому подвластно многое. Кроме того, она отлично выполняла все трюки, а их немало в картине».
Первым трюком, которым неопытная актриса удивила всю съемочную группу, было приручение ослицы Люси – важного действующего лица в фильме. Почему-то это достаточно упрямое животное сразу и безоговорочно полюбило Наталью. Александру Демьяненко для того, чтобы завоевать ее доверие, пришлось потратить целый мешок сахара. Это, по словам Гайдая, «библейское животное» прожило затем долгую и достойную жизнь. Уже в очень преклонном для осла возрасте 55 лет Люся повторно стала звездой экрана, снявшись в фильме «9 рота».
Опытные актеры помогали молодой актрисе, иногда искренне развлекаясь за ее счет. Например, когда снимали сцену похищения, Вицин Моргунов и Никулин так щекотали Наталью в спальнике, что извивалась в кадре она вполне достоверно. А однажды во время съемок, когда от нее требовался веселый и искренний смех, они вдруг вместе задрали майки и стали чесать животы. Сцену сняли без проблем, так как смеялась вся съемочная группа. Наталья Варлей позднее вспоминала дни съемок как очень счастливые, но и тяжелые одновременно:
«За легкостью и веселостью приключений моей героини скрыты тяжелый труд и бесконечные репетиции… Все трюки я выполняла самостоятельно: ныряла в воду, мчалась на машине. Когда работали над эпизодом, где я наезжаю на живую цепочку из моих преследователей, перекрывающих дорогу, я должна была резко затормозить у определенной линии перед кинокамерой. Репетируем — все получается. Начинаем снимать — в последний момент тормоза отказывают… Машина остановилась в каких-то сантиметрах от оператора. Может, потому-то фильм получился таким захватывающим. Мне было тогда 19, и я не задумывалась о риске…»
В фильме, перенасыщенном трюками и юмором, всегда находилось место для новой шутки. Гайдай даже установил цену – бутылка шампанского выдавалась тому, кто придумает что-нибудь новенькое и смешное. Рассказывали, что Никулин в результате заработал 24 бутылки, Моргунов 18, а Вицин одну. Несмотря на свой экранный образ, Георгий Михайлович был абсолютно непьющим человеком. Для него было настоящей проблемой, когда пришлось в кадре выпить кружку пива (под знаменитое « - Жить хорошо! – А хорошо жить еще лучше»). Сначала по его настоянию жидкость заменили на настой шиповника, но потом заметили, что не хватает пены, и актер с огромной неохотой влил в себя настоящее пиво – чего не сделаешь ради искусства!
Один из самых смешных моментов в фильме – шутку с огромным шприцом для Бывалого придумал Юрий Никулин. И даже принес из цирка устрашающий медицинский инструмент. Разумеется, на самом деле его не втыкали в живое тело. Между ног актера поставили табуретку с подушкой, в которую шприц и попадал. Однако Моргунова съемки этой сцены все равно изрядно нервировали, так как игла, хоть и бутафорская, всаживалась со всей силы в опасной близости от его тела.
После окончания съемок и монтажа фильм ожидала обязательная цензурная проверка. И тут, казалось, наступил полный крах. Председателю Госкино СССР Алексею Романову картина категорически не понравилась. Забраковано было практически все – шутки, которые были слишком смелыми, песни, которые оказались двусмысленными, затронутые проблемы – слишком серьезными, в общем, список был так велик, что, казалось, фильму конец. Спасла комедию счастливая случайность. Леониду Ильичу Брежневу, который был большим любителем кинематографа, периодически отсылались новые ленты для просмотра. В один из таких вечеров, когда генсек запросил какую-нибудь свежую комедию, ему отправили забракованную «Кавказскую пленницу», так как больше просто ничего не нашлось. Картина так понравилась Брежневу, что откладывать ее на полку, конечно, после этого не стали. Вот так этот всенародно любимый фильм попал к широкому зрителю.