Leonow urodził się 30 maja 1934 roku we wsi Listwianka w obecnym obwodzie kemerowskim na Syberii. Ukończył uczelnie kształcące pilotów wojskowych i znalazł się w składzie pierwszej w ZSRR grupy kosmonautów, w której był też m.in. Jurij Gagarin.
18 marca 1965 roku stał się pierwszym człowiekiem, który wyszedł w otwartą przestrzeń kosmiczną. Kosmiczny spacer Leonowa w czasie lotu statku Woschod 2 trwał zaledwie 12 minut. Kosmonauta oddalił się od statku na odległość 5 metrów, ubezpieczany liną z kablem telefonicznym. W następnych latach wychodzenie w kosmos stało się zwykłym zajęciem kosmonautów na orbicie, ale to właśnie eksperyment Leonowa pokazał, że człowiek w specjalnym skafandrze może przebywać w otwartej przestrzeni kosmicznej.
Był to także sukces ZSRR w prowadzonej z USA rywalizacji w Kosmosie. Kilka tygodni po Leonowie - 3 czerwca 1965 roku - amerykański kosmonauta Edward Whitte wyszedł na 20 minut z kabiny statku Gemini, połączony z nim przewodem tlenowym i wyposażony w silniczek sterujący.
Historyczne dokonanie Leonowa było jednak otarciem się o śmierć. Kosmonaucie tak napęczniał skafander, że nie mógł z powrotem wcisnąć się przez luk do statku. Wcześniej nie sprawdzono dokładnie stopnia zmian w warunkach nieważkości. Leonow zmniejszył wewnętrzne ciśnienie w skafandrze, co było nadzwyczaj ryzykowne i jakoś przecisnął się do Woschoda 2.
Później w Woschodzie Leonow i jego towarzysz zauważyli, że luk nie domknął się hermetycznie i z kabiny uchodzi powietrze. Włączyli więc automatyczny dozownik tlenu, by wyrównać stratę, co z kolei groziło eksplozją, gdyby po wejściu w atmosferę ziemską zaiskrzył jakiś przełącznik. Zaś w trakcie powrotu Ziemia zawiadomiła ich, że statek nie reaguje na polecenia. Sami przejęli wówczas stery i wylądowali w syberyjskiej tajdze.
Po 10 latach, w 1975 roku, Leonow po raz drugi poleciał w Kosmos i brał udział w połączeniu statków Apollo 18 (USA) i Sojuza 19 (ZSRR) podczas lotu w przestrzeni kosmicznej. W latach 1970-1991 Leonow był wiceszefem centrum szkolenia kosmonautów pod Moskwą. Był także doktorem nauk technicznych, autorem czterech wynalazków i kilkunastu prac naukowych. Po przejściu na emeryturę zasiadał w radach i ciałach konsultacyjnych banków. Należał także do rady rządzącej partii Jedna Rosja.
Kosmonauta zmarł po długiej chorobie w szpitalu w Moskwie. Pożegnanie z Leonowem i pogrzeb na cmentarzu w Mytiszczach pod Moskwą odbędą się 15 października.
