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