Po raz pierwszy Gajdaj pojawił się na ekranie w szalonej komedii muzycznej „Liana” (1955) Borisa Barneta, któremu służył pomocą również jako asystent reżysera. Rok później, wespół z Walentinem Niewzorowem, nakręcił swój fabularny debiut – oparty na opowiadaniach Wadima Korolienki (syna Polaka i Ukrainki, zesłanego na Syberię za działalność polityczną) dramat „Długa droga” („Dołgij put’”), do którego scenariusz napisał inny legendarny twórca, Michaił Romm. W 1958 roku Aleksandr Ałow i Władimir Naumow skorzystali z aktorskich usług Leonida Jowicza, kręcąc „Wiatr”, ostatnią odsłonę swojej – niezbyt wysokich lotów – „Trylogii komsomolskiej”. W tym samym czasie Gajdaj realizował już jednak swój pierwszy w pełni samodzielny obraz. Okazała się nim satyryczna komedia „Narzeczony z tamtego świata” („Żenich s togo swieta”), na planie której po raz pierwszy spotkał się między innymi z Gieorgijem Wicinem, Władimirem Władysławskim oraz Marią Krawczunowską, czyli aktorami, których po latach zaprosi także do udziału w „Operacji Y”. Niestety, film okazał się, jak na standardy radzieckie, zbyt prześmiewczy; cenzurze nie spodobały się przede wszystkim sceny wyśmiewające biurokrację w Kraju Rad. W efekcie – zamiast trafić do szerokiej dystrybucji, obraz pokazywany był tylko w nielicznych kinach, na dodatek o wyjątkowo niesprzyjających porach. Dwa lata później, chcąc przypodobać się władzom kinematografii, reżyser nakręcił – oparty na sztuce Aleksandra Galicza – dramat „Trzykrotnie zmartwychwstały” („Triżdy woskriesszyj”). I poniósł totalną klęskę! Popadł przy tym w depresję, nie bardzo wiedząc, jakie dzieła ma tworzyć, aby spodobały się zarówno jemu, jak i widowni, i na dodatek nie miały kłopotów z cenzurą. Ożywczy okazał się wyjazd z Moskwy do Irkucka, do którego nakłoniła go żona. Tam zupełnie przypadkowo Gajdaj przeczytał satyryczny felieton w partyjnej „Prawdzie”, który uznał za znakomity materiał na film. Przeniósł go na ekran jako „Psa Barbosa” („Pios Barbos i nieobycznyj kross”), który wszedł w skład nowelowego zbioru „Sowierszenno sierjozno” (1961), zrealizowanego pod artystyczną opieką szefa „Mosfilmu” Iwana Pyrjewa. To króciutkie, bo zaledwie niespełna dziesięciominutowe dziełko, okazało się jednak przełomowym, ponieważ to właśnie na jego planie po raz pierwszy spotkało się niezwykłe komediowe trio – Gieorgij Wicin, Jurij Nikulin oraz Jewgienij Morgunow, którzy stworzyli odpowiednio postaci Tchórza, Kiepa oraz Bywałego. Jeszcze w tym samym roku Leonid Jowicz poszedł za ciosem i nakręcił ciąg dalszy „Psa Barbosa”, czyli przezabawną, choć ponownie jedynie krótkometrażową, opowieść o „Bimbrownikach” („Samogonszcziki”).

Jak się okazało, Gajdaj znacznie lepiej radził sobie w krótkich formach, dlatego też kolejny swój film kinowy złożył z trzech niezależnych opowieści opartych na opowiadaniach amerykańskiego klasyka O’Henry’ego. Czarno-biały „Wódz czerwonoskórych” („Diełowyje liudi”, 1962) nie był jednak stylistycznie jednorodny: pierwsza nowela miała charakter dramatyczny, dwie pozostałe – komediowy. Zbiorek nowel cieszył się tak wielkim powodzeniem, że reżyser postanowił nie rezygnować z tej formuły. Napisał dwa kolejne scenariusze, które tym razem dla odmiany miała połączyć postać głównego bohatera – ambitnego, ale bardzo fajtłapowatego studenta Szurika (Aleksandra Timofiejewa). Wielkim problemem okazało się jednak znalezienie odtwórcy tej postaci. Chociaż chętnych nie brakowało, żaden nie spodobał się Gajdajowi. Wreszcie przypadkowo trafił on w gazecie na fotografię Aleksandra Diemjanienki, którego emploi uznał za idealne. Specjalnie też pojechał do Leningradu, aby rozmówić się z artystą. Aktor po latach wspominał: „Kiedy przeczytałem scenariusz filmu, zrozumiałem, że jest on skazany na sukces. Niczego podobnego w naszym kinie dotąd nie było”. Po zrealizowaniu dwóch nowel („Pomocnika” i „Obsesji”) uznano, że całość jest zbyt krótka – trzeba więc było w miarę szybko dokręcić trzecią. Leonid Jowicz sięgnął wówczas po stary i sprawdzony patent, a mówiąc konkretniej – po trio: Kiep, Tchórz i Bywały. W efekcie powstała trzecia opowieść, która dała potem tytuł całemu zbiorowi – „Operacja Y”. Zdjęcia trwały od lipca 1964 do kwietnia 1965 roku; premiera odbyła się cztery miesiące później – 16 sierpnia. Wiele gagów, które przeszły do historii kina radzieckiego, powstawało wprost na planie, a ich autorami byli sami aktorzy. I chociaż film roił się od wpadek technicznych i realizatorskich, widownia zagłosowała na „tak”. W samym tylko 1965 roku obraz Gajdaja obejrzało ponad 69,5 miliona widzów; drugi pod względem popularności film sezonu – dramat Ilji Gurina i Władimira Berensztejna „Wierzcie mi, ludzie” – przyciągnął przed ekrany zaledwie… 40,3 miliona obywateli Kraju Rad. Słowem: „Operacja Y” zdeklasowała rywali! Podobnie zresztą jak i kolejne dzieła Leonida Jowicza. Na „Kaukaską brankę, czyli Nowe przygody Szurika” („Kawkazskaja pliennica, ili Nowyje prikliuczenija Szurika”) w 1967 roku kupiło bilety 76,5 miliona widzów, natomiast na późniejszą o dwa lata „Brylantową rękę” („Brilliantowaja ruka”) – jeszcze dwieście tysięcy osób więcej. Co ciekawe, niewiele brakowało, aby „Kaukaska branka”, zamiast do kin, trafiła na półkę. Film uratował jednak wielki kinoman i jednocześnie… sekretarz generalny Komunistycznej Partii Związku Radzieckiego Leonid Breżniew, któremu komedia Gajdaja spodobała się tak bardzo, że zwolnił ją z aresztu (podobnie zresztą uczynił kilka lat później z innym kultowym radzieckim dziełem, „Białym słońcem pustyni” Władimira Motyla).