Несмотря на небывалый успех "Кавказской пленницы", Гайдай внезапно решил «изменить» комедии — он задумал экранизировать «Бег» Михаила Булгакова. Однако руководству Госкино эта идея не понравилась. Там рассуждали так: Гайдай приносит фантастическую прибыль, снимая комедии, так зачем резать курицу, несущую золотые яйца? А серьезное кино пускай снимают другие режиссеры. (Кстати, «Бег» в 1968 году взялись экранизировать Александр Алов и Владимир Наумов, причем фильм получился прекрасный).

Получив отлуп с «Бегом», Гайдай решил взяться за экранизацию "12 стульев" Ильи Ильфа и Евгения Петрова. Он был давним поклонником этой книги. Тем более, в советском кинематографе еще никто из режиссеров к ней не обращался. В отечественном прокате шла кубинская версия этого романа ("12 стульев", режиссер Томас Г. Алеа, прокат — март 1964 года), однако этот фильм особенных лавров не снискал (его действие разворачивалось на революционной Кубе). Поэтому Гайдай был полон замыслов и энергии снять свою версию бессмертного романа. Он отправился на прием к тогдашнему председателю Госкино А. Романову, но тот мгновенно остудил его пыл. Романов заявил, что другой режиссер — Михаил Швейцер — уже снимает вторую часть дилогии про Остапа Бендера "Золотой теленок" (съемки начались в конце декабря 1966 года), поэтому браться за "12 стульев" сейчас не время: дескать, надо подождать и посмотреть, что получится у Швейцера. Гайдаю не оставалось ничего иного, как согласиться с этим предложением.

Поскольку до окончания работ по "Золотому теленку" было еще далеко (съемки закончатся в январе 1968 года, а готовый фильм выйдет в прокат только в декабре), Гайдай волей-неволей вынужден был взяться за другую работу. И тут как нельзя вовремя подоспел новый сценарий, сочиненный давними партнерами Гайдая Морисом Слободским и Яковым Костюковским. Он назывался «Контрабандист».

Идея этого сценария пришла в голову авторам после прочтения серии статей журналиста Аркадия Сахнина в газете «Правда», посвященных борьбе с контрабандистами. В одной из этих заметок рассказывалось, что преступники используют в своих махинациях весьма оригинальный способ провозки контрабанды — в гипсе. В итоге в начале марта 1967 года на «Мосфильм» поступила заявка на сценарий, а 22 марта со сценаристами был заключен договор. Согласно заявке, сюжет сценария должен был быть таким: простой советский человек Семен Семеныч Павлик (позже его переименуют в Тимошкина, а к началу съемок он обретет свое окончательное имя — Горбунков), отправившись в заграничное турне, совершенно случайно оказался в центре контрабандной махинации: перепутав его со своим коллегой, контрабандисты спрятали в гипсе, наложенном ему на руку, бриллианты. В либретто на заявку говорилось следующее:

"В последние годы советский рубль окреп, завоевал солидные позиции на международной валютной арене. Мы все, естественно, гордимся этим. Но, с другой стороны, это обстоятельство вызвало нездоровый интерес к нашей стране профессиональных контрабандистов. Пользуясь развитием наших международных связей и туризма, контрабандисты стараются забросить в СССР золото и бриллианты, сбыть их и вывезти за границу советские деньги. О таких фактах все чаще и чаще пишет наша печать.

Конечно, в большинстве случаев контрабандисты терпят у нас крах, во-первых, благодаря бдительности соответствующих советских органов, а во-вторых, потому, что деятельность контрабандистов и их клиентов не находит в нашем обществе социальной опоры, так как подавляющее большинство советских людей охотно оказывают помощь государству в борьбе с контрабандой.

История одного такого краха и ложится в основу нашей кинокомедии…"

Практически все лето Слободской и Костюковский писали литературный сценарий будущего фильма. Чуть позже (осенью) к ним присоединился Леонид Гайдай. Поскольку с троицей в лице Балбеса, Труса и Бывалого было решено покончить раз и навсегда (хотя в мае 1968 года в "Советской культуре" Юрий Никулин призывал Гайдая не ставить на троице окончательный крест и продлить ей жизнь в одном из будущих фильмов — идея одного из сценариев была такой: троица, организовав концертную бригаду, отправляется в турне по стране, однако Гайдай, судя по всему, от этих масок устал), в новом сценарии была придумана другая троица: Граф, Механик и Малыш.

31 октября 1967 года в творческом объединении «Луч» состоялось обсуждение сценария «Контрабандист». В целом он был одобрен, но высказывались и отдельные замечания. В частности, было рекомендовано сократить сцены с участием управдомши Плющ, сделать более выпуклой роль милиции (а то, мол, она слишком пассивна), сократить троицу до двух человек, убрав Малыша. Видимо, сценаристы отнеслись к этим поправкам слишком легкомысленно, потому что, когда 29 ноября состоялось новое обсуждение сценария, было принято решение, что рекомендовать его в режиссерскую разработку в таком виде рано, так как он продолжает нуждаться в сокращениях, причем не механических, а сугубо принципиальных.

Разногласия по сценарию удалось разрешить к концу декабря, после чего он был направлен в Главное управление по художественной кинематографии. 30 декабря фильм запустили в подготовительный период. Началось формирование съемочной группы. Себе в помощники Гайдай привлек людей, многие из которых работали с ним впервые. Так, в операторы он взял И. Черных, художником — Ф. Ясюкевича, звукооператором — Е. Индлину. Композитор остался прежний Александр Зацепин.

3 января 1968 года из Главупра пришел ответ, где говорилось, что там согласны запустить режиссерский сценарий в подготовительный период, если в нем будут произведены следующие купюры: сократить эпизод в ресторане с чествованием шефа (он выведен под именем Маврикия), убрать сцену с пионерами, которые поздравляют шефа, убрать реплики: "Как говорит шеф, главное в нашем деле — социалистический реализм", "партия и правительство оставили на второй год". Все эти поправки были учтены.

С 1 февраля начались интенсивные переговоры с актерами, претендовавшими на главные и второстепенные роли, репетиции. Главная роль Семена Семеновича Горбункова — писалась исключительно на Юрия Никулина. Ему даже под это дело в «Союзгосцирке» дали специальный отпуск сроком на полгода, чего ранее никогда не делали. Но Гайдай теперь был в фаворе и мог попросить о таком одолжении кого угодно.

Между тем, на другие роли явных претендентов не было. Вот кто пробовался. Назову лишь некоторых:

Геннадий Петрович Козадоев, он же Граф — Георгий Вицин, Андрей Миронов;

Лелик — Анатолий Папанов, Михаил Пуговкин;

Шеф — Павел Шпрингфельд, Николай Романов, Борис Рунге;

Блондинка Анна Сергеевна — Светлана Светличная, Эве Киви, Юдина;

Жена Горбункова Надя — Ия Саввина, Нина Гребешкова;

Управдом Варвара Сергеевна Плющ — Нонна Мордюкова, Клара Лучко, Татьяна Гаврилова;

Контрабандисты-аптекари — Спартак Мишулин, Леонид Каневский.

8 марта Леонид Гайдай вместе с оператором и директором картины вылетели в Узбекистан для выбора мест натурных съемок эпизодов «заграница». 26 марта эти же люди отправились в Крым для выбора мест натурных съемок эпизодов "город Горбункова". А за четыре дня до этого состоялся худсовет, на котором состоялось утверждение актеров на главные роли. Приведу отрывки из некоторых выступлений.

В. Авдюшко: "Незнакомка — мне больше понравилась Светличная, это не простой ход. Шеф — Шпрингфельд. Есть определенная мягкость в его игре. Миронов выглядит интереснее Вицина…"

Л. Гуревич: "Вицин или Миронов? Все зависит от замысла. Если в старой традции — то Вицин, если по-новому — Миронов. Вицин — не новая роль, а повторение характера, ранее сыгранного.