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