В массовом сознании укрепилось мнение, что режиссёром картины был Георгий Данелия. На самом деле «Джентльменов» снимал Александр Серый, а Данелия вместе с Викторией Токаревой был автором сценария. «Из-за своего несдержанного, ревнивого нрава Саша оказался в тюрьме, — рассказывает Данелия. — Ему дали 8 лет, но вышел он досрочно, через четыре года, не имея ни денег ни работы. Мы с ним дружили, вместе учились ещё на Высших режиссёрских курсах, поэтому я ему предложил: пишу сценарий и становлюсь художественным руководителем картины, а снимает он. На том и порешили».

Идею фильма Данелии и Токаревой подарил известный сценарист Валентин Ежов. Изначально, правда, сюжет был совсем иным: добрый капитан/лейтенант милиции силой убеждения перевоспитывал бандитов, но высшему милицейскому начальству эта задумка не понравилось. В итоге главным героем стал директор детского сада, а его антиподом — рецидивист по кличке Доцент.

Вся блатная речь в картине появилась благодаря Александру Серому — пригодился его тюремный опыт. Плакаты, висевшие в камере: «На свободу — с чистой совестью», «Запомни сам, скажи другому, что честный труд — дорога к дому», а также воровской жаргон: «канай отсюда», «пасть порву, моргалы выколю» — это всё оттуда, с зоны. «Но про «мужика в пиджаке» (памятник Лермонтову) мы с Данелией сами придумали», — вспоминает Токарева.

Итоговый состав актёров также отличался от первоначального. Главная роль сразу были отданы Евгению Леонову. А вот воров-рецедивистов должны были играть Андрей Миронов, Ролан Быков, Юрий Никулин и Савелий Крамаров.

Миронов, Быков и Никулин сниматься отказались. У кого-то не было времени, кто-то был уже занят в других проектах. На роль Хмыря сначала пробовался Лев Дуров, но исполнил этого персонажа Георгий Вицин. Неудачными поначалу были и кинопробы Савелия Крамарова, но Данелия уговорил начальство, и Савелий Викторович стал Косым.

«К тому времени Крамаров снялся у меня в нескольких фильмах, — рассказывал Данелия. — Мне поверили. Правда, когда актёр эмигрировал, его пытались вырезать. Но я им написал, что они совершают идеологическую ошибку. Предложил посмотреть картину внимательнее, ведь актёр Крамаров играет бандита и отщепенца. Подействовало! Оставили всё как было».

Самые большие проблемы были с ролью Василия Алибабаевича. «Меня, знаете, почему взяли? Потому что все беленькие, а Радик Муратов — он чёрный», — рассказывал потом Раднэр Муратов. Его сначала пригласили на эпизодическую роль начальника тюрьмы, но, когда стало понятно, что съёмки надо начинать, а одного из главных героев нет, решили попробовать его.

Курьёзы во время съёмок

Кадр, когда Евгений Леонов едет на верблюде, снимался так: режиссер предложил дрессировщику посадить себе на плечи актёра, спрятаться за верблюда и шагать с ним рядышком. Дело в том, что у Леонова никак не получалось взгромоздиться на верблюда Бориса.

Для съёмок в машине с цементом долго не могли подобрать подходящий раствор. Раднэр Муратов любил рассказывать, как снимали этот эпизод: «Наступил день, когда нас стали туда опускать. Подкатила цистерна с обыкновенной хлебной закваской, подкрашенной зелёной луковой эссенцией. Состав был такой терпкий, липкий... Вылезли мы после съёмок из этого раствора и быстрее мыться, кое-как от себя отскребли его. Смотрим, а Вицина и нет. Оказалось, что он продолжает сидеть в цистерне, потому что узнал, что этот состав на 23 лекарственных травах и на 15 лет продлевает молодость».