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

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

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

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

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

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

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

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

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

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