Po 2. svetovni vojni se je skupaj z družino preselil v Kaliningrad. Šolo je končal leta 1953. V času med februarjem in aprilom leta 1960 so ga izbrali v prvi odred 20-tih sovjetskih kozmonavtov (Skupina 1 Vojnega letalstva). Najprej je bilo mišljeno, da se bo Leonov sprehodil zunaj vesoljske plovila že med odpravo Vostok 11, vendar so to opustili. Tako je sprehod opravil med odpravo Voshod 2, kot drugi pilot, skupaj s Pavlom Ivanovičem Beljajevom. Bil je zunaj vesoljske ladje okoli 5 metrov stran 12 minut 9 sekund (v odprtem prostoru je preživel vsega skupaj 23 minut 41 sekund). Ker se mu je vesoljska obleka v praznem prostoru napihnila, se je le s težavo vrnil v notranjost. Na breztežnost se je prej intenzivno pripravljal 18 mesecev. Poleg tega se je pred vstopom v Zemljino ozračje na ladji pokvaril samodejni sistem za orientacijo. Beljajev je preklopil na ročno upravljanje in vključil zaviralni raketni motor. Pristala sta na nepredvidenem območju 180 km severno od mesta Perm. Dve noči sta morala kozmonavta preživeti v velikem mrazu. Rešila ju je iskalna skupina na smučkah, ki ju je ponesla do zasilnega pristanka helikopterja. Skupaj je njun polet trajal 1 dan 2 uri 2 minuti 17 sekund.
Leta 1967 so ga izbrali za poveljnika Lunine odprave Sojuza. Ker so preskusni leti brez človeške posadke odpovedali in ker je Apollo 8 uspešno opravil podoben let, so odpravo preklicali. Leonov naj bi bil tudi prvi sovjetski kozmonavt, ki bi samostojno pristal na Luni s plovilom LOK/N1. Naslednje leto je Leonov diplomiral na Vojnoletalski inženirski akademiji Žukovskega.
Spet naj bi poveljeval naslednji odpravi k postaji Saljut 1, vendar se tudi to ni zgodilo, zaradi nesreče Sojuza 11, tako da je bila postaja izgubljena. Naslednja dva Saljuta (dejansko vojaški orbitalni postaji Almaz) so izgubili pri izstrelitvi ali kmalu po vtirjenju in Leonova posadka se je morala umakniti. Ko je Saljut 4 dosegel tirnico, so Leonova preusmerili na drug pomembnejši program.
Leonov (drugi z desne) kot član odprave Apollo-Sojuz
Tudi drugi let Leonova v vesolje je bil podobno pomemben. Poveljeval je sovjetskemu delu odprave v programu EPAS, bolj znanem kot Preskusni projekt Apollo-Sojuz, Sojuzu 19, skupaj z ladijskim inženirjem odprave Kubasovom, prvi skupni odpravi med sovjetskim in ameriškimvesoljskim programom. Polet je trajal 5 dni 22 ur 30 minut 51 sekund.
V čin generalmajorja letalstva so ga povišali leta 1975.
Med letoma 1976 in 1982 je bil Leonov poveljnik kozmonavtske skupine in namestnik načelnika Gagarinovega kozmonavtskega vadbenega središča, kjer je nadziral priprave odprav. V letu 1981 je končal adjunkturo na Vojaški inženirski letalski akademiji Žukovskega. Bil je tudi urednik kozmonavtske okrožnice »Neptun«. Upokojil se je leta 1991 in živi v Moskvi. Marca 1992 so ga premestili v rezervne enote. Ima priznane 4 izume in napisal je več kot 10 znanstvenih del.
Leonov je tudi odličen umetnik. Njegova slika Blizu Lune (1968) je zelo podobna otvoritvenemu prizoru iz Kubrickovega filma 2001: Vesoljska odiseja.
