Замысел "Кавказской пленницы" возник у Леонида Гайдая в 1965 году, когда начались съемки первого фильма о незадачливом студенте - "Операция "Ы" и другие приключения Шурика". По словам режиссера, он вместе со сценаристами Яковом Костюковским и Морисом Слободским планировал сочинить и снять еще несколько новелл о Шурике.
Основой второй картины о похождениях студента стали газетные публикации о сохранившейся на Кавказе традиции похищать невесту, остальную часть сюжета авторы придумали. В июне 1965 года Костюковский и Слободской отправили на "Мосфильм" заявку с просьбой одобрить план еще не завершенного сценария "Шурик в горах", состоявшего из двух частей. Первая - "Кавказская пленница" - рассказывала о студентке Нине, приехавшей к родственникам на Кавказ и похищенной местным начальником. Вторая - "Снежный человек и другие" - повествовала о поисках научной экспедицией во главе с известным профессором (его роль предназначалась Михаилу Пуговкину) снежного человека. Его следы ученые находят, но оказывается, что их оставила известная троица - Трус, Балбес и Бывалый - герои, знакомые зрителям по прежним кинокартинам Гайдая. В итоге была утверждена только первая часть.
Готовый сценарий "Кавказская пленница, или Новые приключения Шурика" редколлегия "Мосфильма" обсуждала в октябре 1965 года. Дискуссия развернулась вокруг участия в нем Труса, Балбеса и Бывалого. Некоторые члены редколлегии утверждали, что эти персонажи "утяжеляют" сюжет и действуют "на уже отработанном материале". Отвечая на это замечание, Гайдай сообщил, что троицы в фильме не будет: "Никулин сниматься отказался". Действительно, поначалу исполнитель роли Балбеса счел сценарий неудачным и не захотел играть в "заведомо провальной" картине, однако позже его решение изменилось.
Во второй половине января 1966 года начался подготовительный период. Поиски места для натурных съемок шли сначала на Кавказе, затем в Крыму, где и были найдены подходящие объекты. Кинопробы на "Мосфильме" начались 10 марта. Исполнитель главной роли Александр Демьяненко в них не участвовал - он просто" переместился" в "Кавказскую пленницу" из первой части приключений Шурика. В "Операцию "Ы"" актер попал после того, как через отбор прошли уже около 40 претендентов, в числе которых были Андрей Миронов, Всеволод Абдулов, Виталий Соломин, Александр Леньков, Олег Видов, Евгений Жариков, Александр Збруев. Позже Демьяненко рассказывал, что, прочитав сценарий "Операции "Ы"", сразу понял, что фильм станет успешным - ведь раньше в советском кино ничего подобного не было. Но к своему участию в нем относился критически. "Ну что это: бегаешь туда-сюда?! Мне хотелось чего-нибудь серьезного", - признавался он. В одном из последних интервью Демьяненко сетовал: "Мне уже шестьдесят лет, а я для зрителей все равно Шурик!" Вместе с тем актер понимал, что зрители, видя его, "вспоминают любимые фильмы, улыбаются, а значит, чуточку улучшают свое настроение".
В роли товарища Саахова Гайдай с самого начала задумал снять Владимира Этуша. На выбор повлиял фильм "Время летних отпусков", снятый Константином Воиновым в 1960 году. В нем Этуш сыграл азербайджанского нефтяника Самеда Мамедова, заведующего нефтепромыслом в Сибири. Сам актер позже рассказывал, что после "Времени летних отпусков" регулярно получал приглашения на "восточные роли", которые казались ему невыразительными и однообразными. Тиражировать удачно найденный типаж он не хотел, поэтому "в порыве отрицания" намеревался отказаться и от участия в "Кавказской пленнице". Однако на пробы все-таки пришел и практически сразу был утвержден. Артист отмечал, что в создании образа Саахова ему "помогли" азербайджанцы. В годы Великой Отечественной войны Этуш служил в части, которая формировалась на Кавказе. "Там было полно солдат азербайджанцев и грузин, я с жадностью впитывал эти акценты, мне очень нравилось различать их", - вспоминал он. Так и появились ставшие крылатыми "шляпу сними", "садитэсь пока". Кстати, жена артиста - Нина Крайнова-Этуш, учительница английского языка - родилась в Баку. С ней Этуш познакомился в 1952 году, когда приехал в столицу Азербайджана на гастроли с театром имени Вахтангова. Вместе супруги прожили 48 лет, бывали в Баку у родителей Нины Александровны. "Я помню Девичью башню, Крепость, Дом правительства. Хорошие воспоминания сохранил о людях, с которыми дружил. В Баку нас всегда очень радушно принимали", - рассказывал Этуш.
Знаменитая троица - Балбес, Трус и Бывалый - сформировалась за несколько лет до "Кавказской пленницы". Герои, сыгранные Юрием Никулиным, Георгием Вициным и Евгением Моргуновым, появились сначала в короткометражках "Пес Барбос и необычный кросс" и "Самогонщики", снятых Гайдаем в 1961 году, а затем в "Операции "Ы"". На съемках "Кавказской пленницы" Гайдай и Моргунов поссорились. После этого режиссер вычеркнул из сценария все оставшиеся эпизоды с участием Бывалого. В дальнейшем артисты в таком составе появлялись в фильмах других режиссеров, но Гайдай Труса, Балбеса и Бывалого больше не снимал.
Самым сложным оказался поиск актрисы на роль Нины. В числе претенденток были Лариса Голубкина, Марианна и Анастасия Вертинские, Наталья Фатеева. Пробы проходила и Наталья Селезнева, сыгравшая Лиду в "Операции "Ы"", однако в съемочной группе решили, что Нина не должна ассоциироваться с персонажем предыдущей киноленты. Ассистент режиссера узнала, что на Одесской киностудии в фильме "Формула радуги" снимается "хорошая цирковая девочка" Наталья Варлей, и пригласила ее на пробы. Вспоминая работу над "Кавказской пленницей", Гайдай говорил, что до начала съемок Варлей "ничего не умела делать в кино, но в ней был природный артистизм, которому подвластно многое". Важным для режиссера было и то, что она отлично выполняла все трюки. По признанию же самой актрисы, на премьерном показе в Доме кино она радости не испытывала. Причиной разочарования стало озвучивание: режиссер счел, что Варлей не справилась с закадровой записью голоса, поэтому ее героиню озвучила Надежда Румянцева, а исполняемую Ниной песню про медведей записала Аида Ведищева. Саму песенку Гайдай утвердил не сразу - полагал, что она "не запоминается" и не станет популярной. Всего композитор Александр Зацепин написал семь вариантов мелодии. Возник даже вопрос о его замене, но Никулин и сценаристы убедили Гайдая, что мелодия понравится зрителям. Варлей хотела спеть песню сама, режиссер согласился записать ее, предупредив при этом, что в фильм войдет лучшее исполнение. В этом своеобразном соревновании победила Аида Ведищева, которая позже признавалась, что песенка ей показалась незамысловатой, запись была сделана второпях и заняла не более получаса. "Я смотрела на себя на экране, говорящую совсем не юным голосом и поющую чужим, взрослым, с "вибрато" в припевах, голосом, - и мне становилось плохо", - делилась впечатлениями после премьеры Варлей, отмечая, что "физически ощущала, что нарушена гармония, три компонента не соединяются воедино".
Съемки начались 22 апреля в павильоне "Мосфильма", а 26 мая киногруппа отправилась в Крым. Основную часть натурных съемок провели в Алуште, поселке Лучистое и "Долине Привидений". Сцену "купания" в водоеме снимали на реке Мзымта в Кавказских горах (в районе Красной Поляны), а "похищение невесты" произошло в Абхазии, на дороге к озеру Рица. В конце августа группа вернулась в Москву. В сентябре картину снимали в павильонах, а в октябре началось озвучивание. 16 ноября на "Мосфильме" собрался худсовет, чтобы обсудить "Кавказскую пленницу". Мнения его участников разошлись. Некоторые предполагали, что фильм будет хорошо принят зрителями, отмечая при этом, что обладающий "уникальным дарованием" режиссер несколько "застопорился в своем развитии". Причиной, тормозящей творческие возможности Гайдая, называли пресловутую троицу. Недовольство вызвала и музыка Зацепина. К примеру, песню "Если б я был султан…", которую исполнял Юрий Никулин, сочли "пошловатой", а музыку в целом "устаревшей". В итоге худсовет комедию принять отказался, изложив свои замечания в письменном заключении. 30 ноября частично исправленный фильм был принят дирекцией киностудии практически без нареканий, однако проблемы возникли на следующем этапе. При сдаче комиссии Госкино СССР 23 декабря "Кавказскую пленницу" едва не запретили. Как вспоминал Костюковский, один из киночиновников заявил, что "эта антисоветчина" выйдет на экраны только "через его труп". Через три дня, 26 декабря, ожидалось окончательное решение относительно проката фильма. Однако в его судьбу вмешался Леонид Брежнев, который на выходных попросил показать ему "что-нибудь новенькое". Генеральному секретарю предложили "Кавказскую пленницу", Брежневу комедия понравилась - он даже поблагодарил руководителя Госкино и всю съемочную группу за качественную работу (Кстати, одобрительный отзыв генсека позже решил и участь "Белого солнца пустыни").
6 января 1967 года "Кавказской пленнице" не только дали прокатное разрешение, но и присвоили первую категорию. 1 апреля состоялась премьера в кинотеатре "Художественный", а через два дня фильм вышел на большой экран. В премьерный год комедия стала фаворитом проката - ее посмотрели более 76 миллионов зрителей. В конце 1960-х, на волне успеха, был готов сюжет для продолжения. Согласно замыслу авторов, товарищ Саахов попадает в тюрьму, становится руководителем лагерной самодеятельности. После множества злоключений он оказывается на свободе и хочет возобновить карьеру, однако его должность уже заняла Нина. Сценаристы были уверены в успехе, но Госкино их планы не поддержало. В 2014 году на экраны вышел ремейк комедии Гайдая - "Кавказская пленница!", снятый Максимом Воронковым. В прокате он провалился, в СМИ был нещадно раскритикован, а "старая" "Кавказская пленница" до сих пор остается одной из любимых кинокомедий.