1926 m. vasario 24 d. – gimė Vygrelių kaime, Gražiškių valsčiuje, Vilkaviškio apskrityje. Vaikystėje ir jaunystėje su mama gyveno Kaune.

Nuo 1934 m. – su skautais prie Tautos patriarcho Jono Basanavičiaus paminklo Kaune minėdavo Vasario 16-ąją.

1941–1944 m. – dalyvavo antinacinėje rezistencijoje, platino patriotinius lapelius prieš okupantus.

1944 m. vasarą – įsitraukė į antisovietinių pogrindininkų gretas: dalyvavo Kauno pogrindinėje antisovietinėje organizacijoje, užmezgė ryšius su Tauro partizanų apygardos kovotojais, platino partizanų spaudą.

1948 m. – sovietinės valdžios represinių struktūrų suimtas už priklausymą pogrindinei antisovietinei organizacijai. Suėmimo metu priešinosi ginklu ir nušovė jį bandžiusį suimti sovietų saugumietį.

1948 m. gegužės 3 d. – Karo tribunolo nuteistas kalėti 25 metus: 1949–1956 m. kalintas Balchašo ir Džeskazgano lageriuose, 1956–1973 m. – Mordovijos lageryje. Sunkiai dirbo molibdeno kasyklose, o Džeskazgane lagerio vario kasykloje.

1973 m. – atlikęs visą skirtą bausmę, buvo paleistas į laisvę, be teisės gyventi Lietuvoje. Nepaisydamas draudimo, Kaliningrade pavykus gauti pasą, grįžo į Kauną pas motiną.

1973–1977 m. – dirbo Kauno 5-ojoje elektros montavimo valdyboje. Toliau tęsė pogrindinę veiklą: vertė A. Solženicyno „Gulago archipelagą“, sudarė lietuvių politinių kalinių sąrašą, rinko partizaninio judėjimo dokumentus.

1977 m. balandžio 20 d. – sovietų represinių struktūrų antrą kartą suimtas. Kratos metu buvo rasti Aleksandro Solženicyno knygos „Gulago archipelagas“ vertimo į lietuvių kalbą juodraščiai, užrašai apie sovietinių politinių kalinių padėtį, dokumentai ir tekstai apie žmogaus teisių pažeidimus SSRS. Tuometis teismas Kaune skyrė jam dešimt metų lagerio ir penkerius metus tremties.

1978–1980 m. – kalintas Mordovijos lageryje. 1978 m. lageryje, simboliškai įstojo į Lietuvos Helsinkio grupę.

1979 m. – Europos saugumo ir bendradarbiavimo JAV Kongreso komisija kartu su kitais disidentais pasiūlė Balį Gajauską kandidatu Nobelio taikos premijai.

1980–1987 m. – Kučino (Permės srityje) ypatingojo režimo lageryje. Kalėdamas ypatingojo režimo lageryje rašė publicistinius straipsnius, pasirašydamas savo pavarde su nuoroda, kur parašyta ir kada, kuriuos žmona Irena po pasimatymų lageryje išnešdavo ir juos perduodavo per Rusijos, Ukrainos disidentus užsienio spaudai. Sovietų struktūroms tai išsiaiškinus, pasimatymai buvo nutraukti. Po kalinimo lageryje, sekė dar 2 metai tremties Chabarovsko srityje Čiumikano mieste (tremties laikas buvo iki 1991 m. gruodžio 31 d.). Kalėdamas dalyvavo politinių kalinių akcijose, paremdamas likimo draugų pasipriešinimą lagerio administratorių savivalei.

1981 m. – Hjustone (JAV) Baliui Gajauskui paskirta tarptautinė Taikos ir laisvės premija.

1988 m. lapkričio 7 d. – anksčiau laiko buvo paleistas iš tremties ir grįžo į Lietuvą. Jis ilgiausiai iš visų Lietuvos, o gal ir visos Sovietų Sąjungos politinių kalinių, 37-erius metus buvo kalintas Sovietų Sąjungos kalėjimuose, lageriuose ir tremtyje. Pasak Rusijos disidento ir žurnalisto Michailo Cheifeco: „Balys Gajauskas – pasaulinis kalėjimų rekordininkas.“

1989 m. – Baltų laisvės lygos apdovanotas Laisvės medaliu už kovą išlaisvinant Estiją, Latviją, Lietuvą.

1989 m. kovo – liepos mėn.  gyveno Jungtinėse Amerikos Valstijose, lankėsi JAV lietuvių bendruomenėse Los Andžele, Santa Monikoje, ČIkagoje, Klyvlande, Vašingtone ir kitur. Grįžęs įsijungė į Atgimimo veiklą, dalyvavo politiniame gyvenime. Įsikūrus Politinių kalinių ir tremtinių sąjungai buvo išrinktas valdybos ir tarybos nariu.

1989 m. – išrinktas Politinių kalinių ir tremtinių sąjungos prezidentu.

1990 m. kovo 8 d. – rinkimuose į Lietuvos Aukščiausiąją Tarybą-Atkuriamąjį Seimą išrinktas deputatu Plungės rinkiminėje apygardoje Nr. 71.

1990–1992 m. – Lietuvos Respublikos Aukščiausiosios Tarybos-Atkuriamojo Seimo deputatas. 1990 m. kovo 11 d. balsavo už Lietuvos Respublikos Aktą „Dėl Lietuvos nepriklausomos valstybės atstatymo“. 1990 m. kovo 20 d. – 1992 m. lapkričio 22 d. – Aukščiausiosios Tarybos Krašto apsaugos ir vidaus reikalų komisijos narys, 1991 m. gegužės 8 d. – 1992 m. lapkričio 22 d. – priklausė Jungtinei Sąjūdžio frakcijai.

1992 m. lapkričio 25 d. – 1996 m. lapkričio 25 d. – Lietuvos Respublikos VI Seimo narys. Nuo 1992 m. gruodžio 20 d. iki 1996 m. lapkričio 25 d. – Seimo Nacionalinio saugumo komiteto narys, Seimo komisijos KGB veiklai tirti pirmininkas, politinių kalinių ir tremtinių „Laisvės“ frakcijos pirmininkas.

1992 m. gegužės – rugpjūčio mėn. – Lietuvos Respublikos nacionalinio saugumo tarnybos – Lietuvos Respublikos saugumo tarnybos generalinis direktorius.

1996 m., 2004 m. – dalyvavo Lietuvos Respublikos Seimo rinkimuose.

1989–1997 m. – Lietuvos politinių kalinių ir tremtinių sąjungos prezidentas. 1999–2000 m. – tarptautinės buvusių politinių kalinių ir represuotųjų asociacijos prezidiumo narys. Lietuvos politinių kalinių valdybos ir tarybos narys.

1996–2017 m. – priklausė Permės gubernijos politinių represijų ir totalitarizmo istorijos memorialinio muziejaus tarybai.

2008 m. – išleido knygą „Pro spygliuotas vielas matau dangų“, 2012 m. – „Gulago saulėlydis“. Yra paskelbęs straipsnių politikos klausimais Lietuvos ir užsienio spaudoje.

2000 m. liepos 1 d. – apdovanotas Lietuvos Nepriklausomybės medaliu.

2005 m. birželio 22 d. – apdovanotas Vyčio Kryžiaus ordino Komandoro didžiuoju kryžiumi.

2017 m. rugsėjo 28 d. – mirė Vilniuje. Palaidotas Seniavos kapinėse Kaune.