Сценарно-редакционная коллегия Главного управления художественных фильмов приняла "Операцию "Ы" прохладно. Более того, предложила сократить, а то и вырезать целый ряд эпизодов. Гайдай оставил все как есть, и чуть позже ему это припомнили. Фильм отнесли ко второй категории и потребовали пустить "вторым экраном" - то есть по провинции, с малым количеством копий. Положение спасло письмо Ивана Пырьева председателю Госкино, и 16 августа 1965 года в Москве состоялась премьера новой кинокомедии "Операция "Ы" и другие приключения Шурика".
Кинотеатры брали штурмом, в очереди записывались, кассиры вывешивали аншлаги. Фильм занял первое место в прокате, собрав около 70 миллионов зрителей. Рядом с именами прославленных кинокомиков Вицина, Никулина и Моргунова зажглась новая звезда - звезда Александра Демьяненко.
Теперь актеру невозможно было выйти на улицу. Его узнавали, хлопали по плечу, сразу переходили на "ты", норовили поправить очки, дернуть за ухо. Человек, по природе скромный и неразговорчивый, Демьяненко ненавидел подобные издержки профессии, презирал бесцеремонную фамильярность. Но остановить эту волну было уже невозможно.
Как ни противился Леонид Гайдай, руководство "Мосфильма" заставило его снимать продолжение приключений Шурика. С трудом уговорили вернуться в троицу Никулина. Все понимали, что это последний фильм в таком звездном составе. Но, несмотря ни на что, актеры работали на подъеме, заваливая Гайдая предложениями трюков, гэгов и реприз. В "Кавказскую пленницу" вошло рекордное количество именно актерских находок.
В свою очередь, худсовет "Мосфильма", просматривая черновые материалы, был страшно недоволен. Вот выдержки из заседания: "Троица связывает Гайдая... Она раздражает..."; "Троицу надо бы сократить - на этот раз они все, включая и Никулина, перекривлялись..."; "Демьяненко в начале вял, вообще его можно несколько сократить..."; "Особенно раздражает Вицин..."; "Все трое повторяются и очень кривляются. Перекривлялся даже Демьяненко..."
После ряда рекомендаций Леонид Гайдай перемонтировал картину, и "Мосфильм" ее принял. Однако в Госкино после просмотра заявили, что "Кавказская пленница" никогда не выйдет на экран, а Гайдай положит партбилет на стол.
Спас случай. Фильм не успели отвезти на склад, и он попал на дачу к Леониду Ильичу Брежневу. Генсек от души похохотал и лично поздравил министра кинематографии с новой удачей в советском кино.
В 1967 году "Кавказская пленница" собрала 76 с половиной миллионов зрителей. До этого ни одному советскому режиссеру не удавалось похвастаться такой цифрой. В историю отечественного кино "Кавказская пленница" вошла как самая кассовая комедия.