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