Двадцать третьего декабря 1966 года председатель Госкино Алексей Романов посмотрел «Кавказскую пленницу» и вынес вердикт: «Эта антисоветчина выйдет только через мой труп». Через три дня, 26 декабря, фильм получил высшую категорию, а сам Романов при всех обнял сценариста Якова Костюковского: «Ну что я говорил! Замечательный фильм!»

Что случилось за выходные, Костюковский потом рассказывал не раз. В пятницу вечером из аппарата Леонида Брежнева позвонили на студию и попросили прислать генсеку на дачу «что-нибудь новенькое и весёлое». Подходящей нашлась только что забракованная комедия Леонида Гайдая.
Что не понравилось на «Мосфильме»?
Первыми фильм не приняли свои. 16 ноября 1966 года худсовет объединения «Луч» записал в заключении, что принять картину в нынешнем виде нельзя и нужны поправки. Драматург Эмиль Брагинский назвал песню Юрия Никулина «пошловатой». Эльдар Рязанов предсказывал, что зритель комедию примет, но огорчался, что троица — Трус, Балбес и Бывалый — связывает Гайдая. Художественный руководитель объединения режиссёр Иван Пырьев счёл музыку неудачной и вторичной. Отрывки выступлений приводит в книге о Никулине Фёдор Раззаков, автор книг о советском кино.
Две недели Гайдай сокращал картину и учёл не все замечания. 30 ноября дирекция «Мосфильма» приняла её без поправок. Оставалось Госкино.

Что было в тот выходной?
Генсек смотрел «Кавказскую пленницу» и не по одному разу. В 2001 году Костюковский рассказал «Комсомольской правде»: за выходные Брежнев посмотрел фильм раз пять, позвал всех отдыхающих в санатории ЦК в Барвихе и подсказывал реплики: «А сейчас Никулин скажет, что в соседнем ауле жених украл члена партии». В 2006 году «МК» он пересказал другую версию, со слов дипломата Олега Трояновского, который сидел в том зале: на дачах высокопоставленных лиц картину за выходные прокрутили семь раз, а Брежнев позвонил в Госкино и поздравил с «очередной победой советского кинематографа».
В понедельник, 26 декабря, в Госкино собрались принимать фильм. Накануне знающие люди передали Костюковскому: картину зарубят, а Гайдаю больше не дадут снимать. Но дверь распахнулась, выскочил Романов, обнял сценариста и на весь зал сказал, что фильм замечательный. Кто-то робко спросил, какую категорию давать. «Высшую, конечно», — ответил Романов.
Такой итог голосования называет Раззаков: за первую категорию проголосовали 13 человек, за вторую — трое. Разрешение выпустить картину на экраны сценарно-редакционная коллегия Главного управления художественных фильмов подписала 6 января 1967 года.
Что в фильме всё-таки поменяли?
Высшая категория не отменила замечаний. Трус, как задумали авторы, должен был воскликнуть «Да здравствует советский суд — самый гуманный суд в мире!». Фразу потребовали снять. Ночью Костюковский позвонил Гайдаю и предложил заменить «советский» на «наш». Это разрешили.


Реплику про члена партии должен был говорить Джабраил, дядя Нины, которого играл Фрунзик Мкртчян. Чиновники её запретили. Никулин предложил забрать реплику себе: «Я клоун — у меня пройдёт!» Ему, клоуну, разрешили.
Больше всего досталось «Песне про султана». Пырьев потребовал выбросить её целиком. Сценаристы Костюковский и Морис Слободской подождали, пока он остынет, и показали ему ту же песню без одного куплета. Пырьев просиял: «Это как раз то, что надо!» Выпал куплет о том, как султан приходит домой навеселе. Спустя годы Костюковский искал его для своей книги: ни у кого текста не осталось, пока одна женщина не вспомнила, что полную версию пела её внучка в детском саду «Мосфильма».
Наталья Варлей в роли Нины своим голосом почти ничего не говорит и не поёт: текст озвучила Надежда Румянцева, песню про медведей спела Аида Ведищева.
О Гайдае и Никулине — ещё две истории: как «Бриллиантовую руку» спас ядерный взрыв, которого нет в фильме и кто чуть не сыграл Кузьму Иорданова вместо Никулина.
В первый год «Кавказскую пленницу» посмотрели 76,5 миллиона зрителей.