Как мы помним, еще в конце 60-х, сразу после завершения работы над "Кавказской пленницей", Гайдай собирался перенести на экран прозу Михаила Булгакова — его пьесу «Бег». По ряду причин эта затея не удалась, и «Бег» экранизировали другие. Однако в начале 70-х Гайдай вновь вернулся к идее экранизации Булгакова. Только на этот раз речь уже шла о комедии — пьесе "Иван Васильевич". Ее сюжет вращался вокруг того, как несколько столичных жителей, с помощью машины времени, изобретенной талантливым мастером-самоучкой, перенеслись в эпоху Ивана Грозного, а сам царь оказался в веке XX.

В конце лета 1971 года Владлен Бахнов и Леонид Гайдай подали заявку на сценарий, которая была тут же принята. Осенью сценарий был уже написан и принят сценарно-редакционной коллегией. В начале декабря Гайдай и Бахнов засели за режиссерский сценарий. Эта работа продолжалась до января 1972 года, после чего сценарий был отправлен в Комитет по кинематографии. 3 февраля оттуда пришел ответ, что сценарий в целом принимается, но в него необходимо внести некоторые поправки. В частности, от авторов требовалось, чтобы они перенесли место действия из московского Кремля на другую территорию. Кроме этого, в отзыве говорилось следующее:

"Экскурс в прошлое не должен иметь конкретно-исторический характер; сюжет не следует адресовать определенным историческим лицам. В соответствии с замыслом и жанром произведения эпизоды, в которых воспроизводится прошлое, должны приобрести более условные, приблизительные черты, не относящиеся прямо к Ивану Грозному и его эпохе. Это будет вполне совпадать с поставленной художественной задачей; прошлое возникает не как точный исторический эпизод, а является фантазией изобретателя "машины времени".

В сценарии немало интересной выдумки, однако необходимо предостеречь авторов от излишнего комикования…"

Далее события развивались следующим образом. 8 марта с авторами сценария был подписан договор, 21 марта — сценарий запущен в режиссерскую разработку, 24 мая — утвержден. После этого началось комплектование съемочной группы, строительство декораций, подбор актеров и т. д. Кстати, незадолго до этого к Гайдаю обратился Эльдар Рязанов с предложением взять у него постановку совместной советско-итальянской кинокомедии "Невероятные приключения итальянцев в России". Этот фильм должен был сниматься в жанре эксцентрики, чего Рязанов никогда раньше не делал. Гайдай же в этом деле был настоящий ас. Но Леонид Иович отказался от лестного предложения (в случае согласия ему светила поездка в Италию) и предпочел продолжить работу над "Иван Васильевичем…"