В это время в жизни Леонида произошла встреча, которая стала его судьбой. Однокурсница Нина Гребешкова еще студенткой снялась в пяти фильмах и была уже известна зрителям. Ее даже узнавали на улицах. В 1953 году они поженились и дальше весь свой жизненный путь прошли вместе, разделяя поровну радость и горе.
В 1954 году Гайдаю неожиданно пригодились его актерские и музыкальные навыки. Вместе с однокурсником Марленом Хуциевым их направили режиссерами-стажерами на фильм Бориса Барнета «Ляна», снимавшийся на молдавской киностудии. Барнету Леонид своей худой фигурой напомнил молодого Николая Черкасова в пародийном номере, изображавшем известных датских комиков немого кино Пата и Паташона. Долговязый и тощий Пат был спокоен и невозмутим, суетливый маленький толстяк Паташон вольно или невольно втягивал своего товарища в разные дурацкие ситуации. Эта парочка пользовалась огромной любовью европейских зрителей. Барнет решил снять Гайдая в одной из главных ролей, своеобразного Пата – наивного, влюбленного сельского музыканта. В качестве Паташона выступила партнерша Гайдая по фильму – актриса Муза Крепкогорская – невысокая, плотно сбитая, веселая и темпераментная девушка. Гайдай прекрасно справился со своей ролью, ему прочили прекрасное будущее киноактера. Иван Пырьев даже хотел пригласить его на роль князя Мышкина, но потом передумал, решив, что Гайдай слишком комичен и простонароден для князя. Фильм «Ляна» пользовался огромной популярностью, песню из него пела вся страна, хотя критики встретили картину довольно кисло.
Вообще, Гайдай очень многому научился у Барнета. Леонид Иович говорил, что работа с ним стала для него вторым режиссерским образованием. Тонкая и поэтичная лирика, свойственная Барнету, живой юмор органично сочетались с эксцентрикой и буффонадой, а главные персонажи были обаятельными и милыми чудаками, умело выбирающимися из самых затруднительных положений. Уроки Барнета, его умение работать с актерами Гайдай запомнил на всю жизнь и руководствовался ими во всех своих фильмах. Всю жизнь девизом Гайдая были слова Бориса Барнета: «Пока не ощутишь радость, не снимай кадра». Он писал эти слова в начале каждого своего режиссерского сценария, как эпиграф. По свидетельству композитора Зацепина, много лет сотрудничавшего с Гайдаем, он всякий раз требовал от него написать для фильма песню, которая должна быть такой, «чтобы ее запела вся страна», как песню из фильма «Ляна».
В 1955 году Гайдай окончил ВГИК. Генеральный директор «Мосфильма» Иван Пырьев прислал на него персональную заявку. На «Мосфильме Гайдай некоторое время поработал ассистентом, потом завершал фильм «Долгий путь». Его талант и трудолюбие оценили. Первой самостоятельной постановкой Гайдая стала комедия «Мертвое дело». Сценарий драматургов Владимира Дыховичного и Мориса Слободского одобрили Иван Пырьев и Михаил Ромм, ставший художественным руководителем постановки. Сюжет был таков: у человека на улице вор-карманник украл документы. Потом вора сбила автомашина и он погиб. В милиции решили, что это документы погибшего. А главный герой, живой и здоровый человек, собиравшийся жениться, был объявлен покойником. Он попадает в бюрократический механизм и весь фильм вынужден доказывать, что он – живой. В картине был прекрасный актерский ансамбль: Ростислав Плятт, Георгий Вицин, Вера Алтайская, Рина Зеленая, Сергей Филиппов, Евгений Моргунов, Фаина Раневская и другие актеры. В своих часто цитируемых воспоминаниях Савва Кулиш говорил:
Это поразительная картина была, просто поразительная. Там прекрасные тексты, замечательно играют актеры, а самое главное – там весь ужас того, что есть бюрократия, когда человек не может доказать, что он жив. Она и абсурдистская картина, вообще, это такое очень современное кино.
Фильм получился очень смешным и всем очень понравился, включая Ромма и Пырьева. Не понравился он лишь министру культуры Михайлову, который окончил четыре класса церковно-приходской школы, учился на рабфаке, потом, будучи заведующим сектором печати Пролетарского райкома партии Москвы, окончил три курса факультета журналистики МГУ, но так и остался малограмотным. Министр культуры, он не мог даже выговорить слово «кинематография», которой руководил, и употреблял изобретенный им термин «кимография». Главным в кино Михайлов считал соответствие партийным установкам и идеологическое рвение. Это о нем была поговорка: «Бояться надо не министра культуры, а культуры министра». Узнав, что Гайдай одним из своих учителей считал Барнета, Михайлов, считавший своим учителем сталинского идеолога, мерзавца и негодяя Андрея Жданова, вспомнил, как тот обзывал творчество Барнета зубоскальством и злопыхательством. После просмотра фильма Гайдая «Жених с того света», где весь зрительный зал хохотал, Михайлов грозно спросил: «Вы член партии?», на что Гайдай ответил: «Да. Вступил на фронте».
Михайлов подтвердил свои худшие опасения – фронтовики были свободнее тех, кто сидел в тылу и выжимал из народа последнее. «Вы мне положите партбилет за этот пасквиль на советскую действительность».
На этом разговор был окончен. Гайдаю объявили строгий выговор и запретили снимать кино. Фильм сократили вдвое, перемонтировали, частично пересняли и переозвучили. Многие эпизоды и прекрасные актеры, блестяще сыгравшие свои роли, исчезли вовсе. Изуродованную картину все же выпустили в прокат под названием «Жених с того света». Гайдай страшно переживал. Именно в это время он заболел туберкулезом легких. От исключения из партии Гайдая спас Пырьев, который ему симпатизировал. Он собрал на Мосфильме конференцию кинокритиков и журналистов и поставил вопрос: «Нужна ли в СССР эксцентрическая комедия?». Зал вяло отвечал на вопрос, и тогда Пырьев запер двери и заявил, что никто не выйдет отсюда, пока четко и ясно не ответит на его вопрос. Все знали, каков бывает Пырьев в ярости, и быстро написали положительные ответы. Это спасло молодого режиссера. И снова Гайдая выручил Пырьев. Он вызвал Леонида в свой кабинет, сказал: «Тебя спасет только одно – историко-революционный фильм». И положил перед ним давно купленный студией сценарий Александра Галича по его же пьесе «Пароход зовут „Орленок“». Пьеса писалась в середине 1950‐х годов.
Сюжет был таков: в 1919 году красногвардейцы на паровом буксире сражались с белыми. Потом буксир возил грузы по Волге, а во время войны перевозил детей и раненых из осажденного Сталинграда. Теперь он стоял на приколе в затоне, ожидая пока его порежут на металлолом. Но пионеры вместе с детским врачом тайно устроили там музей революции. В это время комсомольцы везут подарки строителям гидроэлектростанции, их машина ломается, и единственной возможностью добраться на праздник вовремя становится этот буксир. Пионеры и комсомольцы при поддержке партийных работников восстанавливают его и отправляются в плавание. Пьеса ничем не напоминает того Галича, который получил известность в 1960‐х годах как автор сатирических песен, но отражает его громкий успех в качестве драматурга, чьи пьесы, такие как «Город на заре» и «Вас вызывает Таймыр», с аншлагами шли в театрах в 1940–1950‐е годы.
Гайдай от безысходности взялся за чуждую ему тему и трудился над фильмом с полной отдачей. Картина понравилась начальству. Гайдая вновь вернули в стан кинорежиссеров, но сам Леонид Иович получил от переживаний язву желудка и никогда не упоминал «Трижды воскресшего» в числе своих работ. После сдачи фильма он уехал в Глазково к родителям. По воспоминаниям Нины Гребешковой:
После каждой картины Леня рвался сюда, во-первых к родителям, а во-вторых, чтобы залезть на чердак и почитать то, что было у него в юности, эти старинные журналы… И вот однажды, в очередной приезд, спускается он оттуда и говорит: «Нинок, я написал сценарий. Вот давай я тебе почитаю». Сценарий был «Пес Барбос и необычный кросс». И вот, он мне читает: «пес Барбос – два метра, Бывалый, повернулся, отвернулся» – все по полтора, два метра – и говорит: «правда, смешно?» А я, чтобы его поддержать, говорю: «Да, Леня, смешно». Но, в общем, веры в то, что это смешно, у меня не было. Но у нас были такие отношения, что мне его всегда хотелось поддержать.
Непосредственным поводом для фильма стал напечатанный в «Правде» фельетон украинского поэта Степана Олейника «Пес Барбос и необычный кросс». А Олейнику, возможно, попал в руки рассказ английского писателя Уильяма Джекобса «Заряженный пес», рассказывавший такую же историю. У Олейника главным героем был сельский браконьер Гаврила Щур, а два его подельника были совершенно безликими персонажами. Гайдай придумал им точные образы и характеры, создав блестящую комедийную троицу: Бывалого, Труса и Балбеса. Фильм снимался осенью 1960 года. Актерам, да и всей съемочной группе, пришлось бегать с утра до вечера, и к концу дня они буквально валились с ног. Гайдай удивил всех, лично отслеживая с секундомером ритм и скорость каждого кадра. Он и монтировал картину, безжалостно вырезая все лишнее. Из отснятого материала можно было собрать тридцатиминутный фильм, но в итоге картина длится менее десяти минут, не давая зрителям возможности расслабиться ни на секунду.
«Пса Барбоса» показали вне конкурса на закрытии Московского международного кинофестиваля после вручения призов. Режиссера при этом не сочли нужным пригласить на премьеру собственного фильма, и Гайдай не видел, как на его картине покатывались со смеху звезды мирового кино. Утром следующего дня к Гайдаю пришел Сергей Бондарчук. Он был соседом по дому и председателем жюри кинофестиваля и, посмотрев короткометражку, был так впечатлен, что ночью нарисовал на тарелке портрет пса Барбоса, и вручил Леониду свой собственный приз – тарелку со словами поздравления. «Пес Барбос» имел потрясающий успех. Его купили для проката сто две страны мира.
После этого Гайдай снял короткометражный фильм «Самогонщики», развивавший стилистику «Пса Барбоса» и с теми же актерами. Сценарий написал Леонид Гайдай вместе с оператором Константином Бровиным. И хотя фильм имел почти такой же успех, как предыдущий, кинокритики признали его эксплуатирующим уже ранее найденные приемы. Гайдай признал, что критики правы, и решил снять совсем другое кино. Следующим его фильмом стал уникальный по жанру сборник «Деловые люди», по рассказам американского писателя О. Генри.