Er entstammte einer Bauernfamilie und wurde 1901 im südrussischen Bezirk Sernograd bei Rostow am Don geboren. Im Russischen Bürgerkrieg kämpfte er zunächst beim Reiterkorps des Obersten B. M. Dumenko gegen die Don-Kosaken. 1919 trat er in die 1. Rote Reiterarmee ein und nahm an den Operationen bei Woronesch-Kastornoje, am Donbass und bei Jegorlyksk teil. Im September 1919 übernahm er bei der Südfront die 1. Don-Kavallerie-Brigade und im Dezember führte er die 1. Kavallerie-Division bei der 10. roten Arme. Im März 1919 wurde er mit dem Rotbannerorden ausgezeichnet.
Als die Rote Armee die ersten mechanisierten Einheiten bildete, begann seine zukünftige Laufbahn bei den mobilen Panzertruppen. Seit 1924 wurde er Mitglied der KPdSU. Im Jahr 1933 absolvierte er die Frunse-Militärakademie und befehligte nacheinander ein Panzerbataillon und ein Panzerregiment. 1938 wurde er zum Oberst ernannt und befehligt beim Einmarsch der Roten Armee in Ostpolen und ab Dezember 1939 im Finnischen Winterkrieg die 39. selbständige Panzer-Brigade, die noch vorwiegend mit leichten T-26 ausgestattet war. Anfang April 1940 wurde er zum Brigadegeneral ernannt, durch ein Dekret des Präsidiums des Obersten Sowjets wurde ihm am 7. April 1940 der Ehrentitel “Held der Sowjetunion” zuerkannt.
Im Deutsch-Sowjetischen Krieg
Am 6. April 1941 wurde er zum Generalmajor befördert und erhielt das Kommando über das 21. mechanische Korps. Während der deutschen Invasion in der Sowjetunion (Juni 1941) kommandierte er sein Korps (mit BT-7 und T-26 Panzer) im Bereich der 11. Armee im Raum Dünaburg. Obwohl seine Truppen durch das deutsche LVI. Panzerkorps innerhalb dreier Wochen über 450 km zurückgedrängt wurde, erhielt er den Orden des Roten Sterns. Im August 1941 wurde Leljushenko von Stalin beauftragt, 22 neue Panzerbrigaden aufzustellen, die mit den kampfstärkeren Panzertypen T-34 und KW-1 ausgerüstet wurden. In dieser Zeit hatte er zahlreiche spätere Panzerführer, wie Rotmistrow, Katukow und Solomatin unter seinem Kommando. Ende September wurde die Situation südwestlich der Moskauer Schutzstellung so kritisch, dass ihn die Stawka mit der Bildung der ersten Welle mehrerer Schützenkorps beauftragte, die speziell die Autobahn von Orel nach Tula zu decken hatten. Nach dem Verlust von Orel und Mzensk überschritten die deutschen Truppen Anfang Oktober den Suscha-Abschnitt.
Katukows 4. Panzerbrigade war mit den neuen T-34 ausgestattet und bekämpfte u. a. in der Panzerschlacht bei MzenskGuderians Panzergruppe erfolgreich. Leljuschenko erhielt in dieser Zeit den Oberbefehl über die 5. Armee im Raum Moschaisk. Eine seiner Panzerbrigaden zeichnete sich bei der Abwehr entlang der Moskauer Autobahn im Raum Borodino aus. Mitte November übernahm Leljushenko während der Schlacht um Moskau die Führung der 30. Armee. Bei der sowjetischen Gegenoffensive, die am 5. Dezember gestartet wurde, drang die ihm unterstellte 371. Schützendivision tief durch die deutschen Linien nach Westen vor.
Am 1. Februar 1942 erfolgte seine Rangerhöhung zum Generalleutnant. Am 14. Oktober 1942 übernahm er bei der Donfront das Kommando über die im Raum Stalingrad eingesetzte 1. Gardearmee, welche bereits wenige Tage darauf aufgelöst wurde. Schon Anfang November übernahm er die neu formierte 1. Gardearmee, welche am mittleren Don-Abschnitt durch Umbenennung der 63. Armee geschaffen wurde. Bei der Operation Uranus, der Umfassungsoperation der deutschen 6. Armee, waren seine neuen Truppenverbände maßgeblich am Erfolg beteiligt. Am 16. Dezember beteiligte sich seine Armee, die jetzt in 3. Gardearmee umbenannt worden war, erfolgreich an der Operation Saturn, dabei drangen seine Truppen 100 Kilometer tief in das gegnerische Hinterland vor. Im Jahr 1943 stand seine Armee fast ganzjährig bei TolbuchinsSüdfront und beteiligte sich an der Freikämpfung des Donbass.
Mitte Februar 1944 wurde seine Armee während der Dnepr-Karpaten-Operation der 1. Ukrainischen Front zugeteilt und nahm ab Anfang März an der Proskurow-Czernowitzer Operation teil. Am 29. März 1944 trat er die Nachfolge von General Badanow an und übernahm während der Einkesselung der deutschen 1. Panzerarmee (Hube) im Raum Kamenez-Podolsk die Führung der 4. Panzerarmee. Ab 13. Juli 1944 kam die 4. Panzerarmee in der Lemberg-Sandomir-Operation zum Einsatz, in der es gelang die Hauptstadt von Galizien, Lemberg am 27. Juli zu befreien. Nach einem weiteren Vorstoß von 200 Kilometer Tiefe bildeten seine Verbände Mitte August den Weichselbrückenkopf von Sandomierz. Am 5. November 1944 wurde er zum Generaloberst befördert.
Im Januar 1945 während der Weichsel-Oder-Operation erreichten seine Truppen über Kielce und Radomsko vorgehend Glogau und bildeten einen Brückenkopf über die Oder. Im Rahmen der Niederschlesischen Operation erreichten seine Truppen den Raum Forst. Am 17. März wurde die 4. Panzerarmee in 4. Garde-Panzerarmee umbenannt und nahm unter Marschall Konew ab Mitte April an der Berliner Operation teil. Nach der Kapitulation Berlins wurde die Armee nach Süden verlegt, um an der Prager Operation teilzunehmen. Am 5. Mai überschritten seine Truppen die Elbe und erreichte über das Erzgebirge auf Teplitz vordringend am 9. Mai Prag.
Nachkriegszeit
Armeegeneral Leljuschenko beim Besuch des 81. Garde-MotSchützenregiments in Eberswalde in der ehemaligen Artilleriekaserne 1984, das Regiment war Teil der 20. Gardearmee, die er 1944–47 befehligte
Bis 1946 führte er die 4. Panzerarmee in Deutschland. Danach wurde er oberster Befehlshaber aller gepanzerten Streitkräfte der sowjetischen Besatzung in Ost-Deutschland. Ab März 1950 wurde er Kommandeur der 1. Rotbannerarmee in Fernost. Ab Juli 1952 war er stellvertretender Befehlshaber im Militärbezirk Karpaten. Von November 1953 bis zum Januar 1956 befehligte er die 8. Panzerarmee im Militärbezirk Karpaten. Im Januar 1956 übernahm er die Führung des Militärbezirks Transbaikalien und ab Januar den Militärbezirk Ural. Am 8. Mai 1959 wurde er zum Armeegeneral befördert. Seit Juni 1960 war er Vorsitzender des Zentralkomitees der DOSAAF. Seit Juni 1964 war er Militärberater bei der Generaldirektion des Verteidigungsministeriums. Vor seiner Pensionierung war auch Abgeordneter im Präsidium des Obersten Sowjets. Er verstarb im Juli 1987 in Moskau und wurde am Nowodewitschi-Friedhof beigesetzt.
