Maršál Jerjomenko se narodil roku 1892 v Markivcích u Luhansku. Rolnický synek z vesnice na východě Ukrajiny byl povolán do ruské armády roku 1913, stal se poddůstojníkem, ale brzy na to roku 1915 patrně dezertoval. Není známo, co dělal potom, ale koncem roku 1918 vstoupil se svým údajně partyzánským oddílem do Rudé armády. Zúčastnil se občanské války a sovětsko – polské války a sloužil v 1. jezdecké armádě pozdějšího maršála Buďonného, kde se také blíže seznámil s K. J. Vorošilovem. Mezi válkami absolvoval vyšší vojenská studia na Vojenské akademii Rudé armády a jeho přátele z 1. jezdecké armády ho zřejmě zachránili před Stalinovou masovou čistkou důstojnického sboru v letech 1937 – 1938.

Po účasti na okupaci východní části Polska na podzim 1939 a Litvy o rok později byl na krátkou dobu poslán na Dálný východ. Odtud se vrátil, aby sloužil za sovětské protiofenzívy u Moskvy na podzim a v zimě 1941 v různých velitelských funkcích. V říjnu 1941 byl těžce raněn, do služby se vrátil v prosinci a v únoru 1942 byl znovu raněn. Ne zcela vyléčen převzal v srpnu 1942 velení vojsk Jihovýchodního frontu, o měsíc později přejmenovaného na Stalingradský. Byl jedním z rozhodujících sovětských velitelů, kteří hájili Stalingrad a nakonec zde obklíčili německou 6. armádu. Jeho vojska odrazila pokus skupiny armád Don generála von Mansteina vyprostit obklíčené německé vojáky.

Když v létě 1943 Jerjomenko velel Kalininskému frontu před Smolenskem, stalo se jeho velitelské postavení u Rževa 1. srpna cílem kuriózní jediné návštěvy tehdejšího maršála SSSR a vrchního velitele, J. V. Stalina. Stalinovo okolí rychle pochopilo, jaký byl účel této návštěvy na frontě. Jeho frontový hostitel Jerjomenko, měsíc na to navrhl, aby Stalin obdržel Suvorovův řád první třídy za Stalingrad a za to, že dával neocenitelné příkazy, jež zajistily vítězství na Kalininském frontu. Jež měly kořeny v návštěvě fronty vrchním velitelem ozbrojených sil. V dalším průběhu války zastával generál Jerjomenko velitelské funkce při bojích na Krymu, Litvě, v Karpatech a na závěr války při Ostravsko – opavské a Pražské operaci. Hodnost maršála Sovětského svazu mu byla udělena 11. března 1955.