1942年8月,任[[东南方面军]]司令员,负责阻止德军向[[斯大林格勒]]方向的进攻。9月28日,东南方面军改番号为[[斯大林格勒方面军]],在之后的四个月,叶廖缅科指挥该方面军在斯大林格勒与德军进行持久惨烈的巷战,将[[第6集团军(纳粹德国)|德军第6集团军]]牵制在斯大林格勒。
1942年11月,在[[天王星行动]]中,指挥斯大林格勒方面军向斯大林格勒以南发起进攻,并与[[尼·费·瓦图京]]指挥的[[西南方面军]]会师,完成对德军第6集团军的包围。12月,组织部队在[[科捷利尼科沃战役科捷利尼科夫斯基战役]]中将[[埃里希·冯·曼斯坦因]]的德军救援部队阻击在红军的包围圈之外。
1943年1月1日,斯大林格勒方面军改名为[[南部方面军]],并继续向[[顿河畔罗斯托夫]]方向追击敌军,战线向前推进了200公里,但由于进攻力量不足,未能大量消灭敌人有生力量。