Как мы помним, еще в конце 60-х, сразу после завершения работы над «Кавказской пленницей», Гайдай собирался перенести на экран прозу Михаила Булгакова — его пьесу «Бег». По ряду причин эта затея не удалась, и «Бег» экранизировали другие. Однако в начале 70-х Гайдай вновь вернулся к идее экранизации Булгакова.
Только на этот раз речь уже шла о комедии — пьесе «Иван Васильевич». Ее сюжет вращался вокруг того, как несколько столичных жителей, с помощью машины времени, изобретенной талантливым мастером-самоучкой, перенеслись в эпоху Ивана Грозного, а сам царь оказался в веке XX.
В конце лета 1971 года Владлен Бахнов и Леонид Гайдай подали заявку на сценарий, которая была тут же принята. Осенью сценарий был уже написан и принят сценарно-редакционной коллегией. В начале декабря Гайдай и Бахнов засели за режиссерский сценарий. Эта работа продолжалась до января 1972 года, после чего сценарий был отправлен в Комитет по кинематографии.
3 февраля оттуда пришел ответ, что сценарий в целом принимается, но в него необходимо внести некоторые поправки.
В частности, от авторов требовалось, чтобы они перенесли место действия из московского Кремля на другую территорию. Кроме этого, в отзыве говорилось следующее: «Экскурс в прошлое не должен иметь конкретно-исторический характер; сюжет не следует адресовать определенным историческим лицам.
В соответствии с замыслом и жанром произведения эпизоды, в которых воспроизводится прошлое, должны приобрести более условные, приблизительные черты, не относящиеся прямо к Ивану Грозному и его эпохе.
Это будет вполне совпадать с поставленной художественной задачей; прошлое возникает не как точный исторический эпизод, а является фантазией изобретателя «машины времени».
В сценарии немало интересной выдумки, однако необходимо предостеречь авторов от излишнего комикования…»
Далее события развивались следующим образом. 8 марта с авторами сценария был подписан договор, 21 марта — сценарий запущен в режиссерскую разработку, 24 мая — утвержден. После этого началось комплектование съемочной группы, строительство декораций, подбор актеров и т. д.
Кстати, незадолго до этого к Гайдаю обратился Эльдар Рязанов с предложением взять у него постановку совместной советско-итальянской кинокомедии «Невероятные приключения итальянцев в России». Этот фильм должен был сниматься в жанре эксцентрики, чего Рязанов никогда раньше не делал. Гайдай же в этом деле был настоящий ас. Но Леонид Иович отказался от лестного предложения (в случае согласия ему светила поездка в Италию) и предпочел продолжить работу над «Иван Васильевичем…»
В качестве своих помощников в работе над фильмом Гайдай выбрал людей, с которыми работал еще над «12 стульями». Оператором взял Сергея Полуянова (вторым оператором был новичок в группе — Виталий Абрамов), художником Евгения Куманькова, звукооператором — Раису Маргачеву, композитором Александра Зацепина, директором — А. Ашкинази.
С актерами была похожая ситуация: Гайдай намеревался работать с теми, кого давно знал. Но планы пришлось подкорректировать. Например, на главную роль — царя Ивана Грозного и Бунши — он собирался пригласить Юрия Никулина. Однако у того был слишком плотный график гастролей в цирке и добиться разрешения у «Союзгосцирка», чтобы его освободили, так и не удалось.
Гайдай очень сильно переживал по этому поводу, но поделать ничего не мог пришлось искать другого исполнителя. Им стал актер Театра имени Вахтангова Юрий Яковлев, с которым до этого Гайдай никогда еще не работал (он выиграл спор у Евгения Лебедева).