Sündis 1923. aastal NSVL-s linnas nimega Svobodnyi. Isa oli raudtetööline, ema oli pärit Rjaasani oblastist. Tal oli ka vend Aleksander ja õde Augusta. Gaidai õppis raudtee koolis nr. 42. Ta võttis osa teisest maailmasõjast, kus sai raskelt haavata ning tunnistati rivikõlbmatuks.
1947. aastal lõpetas teatristuudio Irkutski oblasti draamateatris, töötas valgustaja ja näitlejana. 1949. aastal asus õppima režissööriks (VGIK-s), mille lõpetas 1955. aastal. Stsenaariumid oma filmidele kirjutas ta pea alati ise. Paljud fraasid tema filmidest saavutasid suure populaarsuse inimeste seas.
Oli abielus näitlejanna Nina Grebeshkovaga. Gaidai suri 1993. aastal ja on maetud Kuntsevski kalmistule Moskvas.