Барон Мюнхгаузен существовал на самом деле. Его звали Карл Фридрих Иероним фон Мюнхгаузен, он родился в XVIII веке в Германии, в 18 лет уехал в Россию и стал ротмистром русской службы. В 1744 году он командовал почётным караулом, встречавшим в Риге невесту цесаревича — принцессу Софию-Фредерику Ангальт-Цербстскую (будущую императрицу Екатерину II). В том же году он женился на рижской дворянке Якобине фон Дунтен, и они прожили вместе больше сорока лет. Литературным персонажем барон стал благодаря писателю и историку Эриху Распе, который выпустил сборник его рассказов под названием «Лживые или вымышленные истории».

История захаровского фильма началась с театральной постановки. Владимир Зельдин попросил драматурга Григория Горина написать пьесу о бароне Мюнхгаузене — актёр мечтал сыграть этого героя, но не было подходящего материала. Горин взял за основу сюжеты немецкого писателя Эриха Распе и написал пьесу «Самый правдивый». Поставленный по ней спектакль назывался «Комическая фантазия…» и шёл в Театре Советской армии с невероятным успехом! Посмотрев постановку, режиссёр Марк Захаров решил немедленно перенести её на экран. Если бы Захаров оставил в главной роли Зельдина, получился бы совсем другой фильм. Но у Захарова были свои принципы: режиссёр «Ленкома» обожал труппу своего театра, и костяк всех его фильмов составляли именно его актёры.

В образе барона Мюнхгаузена режиссёр Марк Захаров видел только Олега Янковского, хотя против него были и худсовет, и сценарист Григорий Горин (который настойчиво предлагал на роль Андрея Миронова). Амплуа Янковского до этого, как считалось, более соответствовали героические роли. Кроме того, сложившийся по книге и спектаклю образ барона соответствовал немолодому человеку, имеющему взрослого сына. Янковскому же на момент начала съёмок исполнилось только 35 лет. В итоге режиссёру удалось отстоять свою точку зрения. Потом Горин признавался, что взять другого актёра было бы непростительной ошибкой.

На роль баронессы Якобины фон Мюнхгаузен Захаров пригласил приму своего театра Инну Чурикову, будучи уверенным, что ленкомовская звезда блестяще сыграет покинутую супругу главного героя. Так и произошло, фразы баронессы из уст царственной Инны Михайловны звучат шедеврально: «Завтра годовщина твоей смерти. Ты что, хочешь испортить нам праздник?» Кстати, Чурикова попросила, чтобы на роль её сына Феофила взяли Леонида Ярмольника. Но, как вспоминает Ярмольник, на съемках она была к нему невероятно требовательна и во время дублей с пощечиной молодого человека не щадила, била по-настоящему: «Чтобы было убедительнее».

На роль Марты режиссёр хотел утвердить Татьяну Догилеву, но худсовет кандидатуру отклонил. На роль пробовались Галина Золотарёва, Ирина Мазуркевич и другие актрисы, среди которых была Елена Коренева. Создатели картины разложили фотографии всех претенденток и выбрали Кореневу, несмотря на то, что на фото она вовсе не была похожа на романтическую героиню — у нее была стрижка «под мальчика».

В пользу Кореневой сыграло и то, что она не была актрисой захаровского «Ленкома» — в фильме и так была занята солидная часть труппы. «Если всех забрать на съемки, кто же в театре будет играть?» — заметил Марк Анатольевич.

Съёмки проходили в немецком городе Вернигероде. В массовке и эпизодах принимали участие немецкие актёры, был и немецкий каскадёр. Как-то Александр Абдулов предложил ему помериться силами — побороться даже не на руках, а на пальцах. Сцепились указательными пальцами, начали друг на друга напирать, и тут раздался хруст… Немецкий каскадёр случайно вывихнул Абдулову палец! Пришлось накладывать гипс, и Захаров был жутко недоволен таким ребячеством.

В ходе дальнейших съёмок Абдулов умудрился сломать ещё и палец на ноге

Об этом рассказал уже Марк Захаров: «Не сломал, вывихнул. Абдулов — очень азартный человек и уговаривал меня разрешить ему прыгнуть с четырехметрового забора без дублера. Второй режиссер — человек более опытный — сказал, что нужно сделать специальную яму, смягчающую удар о землю, еще что-то. Я отнесся к этому легкомысленно. В результате Александр Гаврилович сиганул и повредил себе ногу. Я очень сожалел, что уступил ему. Был еще один эпизод, сопряженный с риском для Янковского, когда его герой лезет по веревочной лестнице. Я сам сначала попробовал, ступеньки из-под ног уходят, страшно. Но Янковский без дублера и страховки поднялся на приличную высоту».

На момент съемок в картине «Тот самый Мюнхгаузен» в роли курфюрста Ганновера Леонид Сергеевич ещё не состоял в труппе «Ленкома»: туда он придёт лишь в 1988 году и прослужит до самой смерти. Но Захаров, по всей видимости, чувствовал «своих» актёров: он приглашал Броневого сниматься во все свои фильмы без проб. Так было и в этот раз. Леонид Сергеевич в роли курфюрста Ганновера с его заявлениями — «Свободная линия плеча, зауженные панталоны… Вы могли бы стать примером для нашей молодежи!» — оказался блистателен. А интонацию для героя позаимствовали у тогдашнего директора киностудии «Мосфильм», который каждую свою фразу начинал словами: «Ну-у… Задумано у тебя, конечно, интересно…»

Знаменитая фраза барона Мюнхгаузена: «Умное лицо ещё не признак ума…» — в сценарии звучала как «Серьёзное лицо ещё не признак ума…» Олег Янковский случайно оговорился, но новый вариант очень понравился Марку Захарову. Он оставил его в фильме, несмотря на протесты сценариста Григория Горина.