В конце января 1942 года в состав Закавказского фронта была передана 51-я армия, переправившаяся из Крыма на Таманский полуостров.
В июле 1942 года Федор Иванович Толбухин получил назначение на должность командующего 57-й армией Сталинградского фронта. Его армия сыграла важную роль в битве за Сталинград. В оборонительный период сражения 57-я армия была развернута в междуречье Дона и Волги, преградив немцам подступы к городу на юго-западном направлении. Взаимодействуя с 64-й армией, против которой были направлены основные силы противника, соединения Толбухина остановили продвижение немецких частей в районе Абганерово, Плодовитое, Тингута.
В августе 1942 года 4-я танковая немецкая армия генерала Гота, возобновив наступление, обрушила основной удар на 57-ю армию Толбухина. Свыше трех месяцев соединения армии вели тяжелые оборонительные бои, в ходе которых наиболее полно проявился полководческий талант командующего армией. Толбухину удавалось своевременно предугадывать замысел противника, он умело маневрировал резервами, вовремя выдвигая их на направления главных ударов. Толбухин поражал подчиненных командиров и штабных офицеров своей организованностью, спокойствием, уверенностью в принимаемых решениях, высокой штабной культурой. Он всегда стремился нанести по противнику внезапный удар. В оборонительных боях немцам был причинен значительный урон, и все их попытки прорваться к городу терпели неудачу.
На втором этапе сражения за Сталинград армия Толбухина вошла в состав ударной группировки войск Сталинградского фронта.
В развернувшемся 19 ноября контрнаступлении 57-я армия сыграла решающую роль. Прорвав оборону противника, она соединилась 23 ноября в районе хутора Советский с войсками Юго-Западного фронта. В последующем, войдя в состав Донского фронта в январе 1943 года, армия принимала активное участие в ликвидации 6-й немецкой полевой армии фельдмаршала Паулюса.
За Сталинград Толбухин был отмечен орденом Суворова I степени, и ему было присвоено очередное звание генерал-лейтенанта.
После окончания Сталинградской битвы, в марте 1943 года, Толбухин назначается командующим войсками Южного фронта, а 28 апреля ему присваивается звание генерал-полковника.
Первой операцией в должности командующего фронтом для Толбухина стала операция по прорыву обороны противника на реке Миус. Немцы объявили Миус нерушимой границей Германии на востоке. Ее оборона начала создаваться еще в 1941 году и все это время продолжала совершенствоваться. К лету 1943 года оборона достигала в глубину 40—50 километров и состояла из трех полос, на которых располагались минные и проволочные заграждения, мощные доты и дзоты.
Отвлекая и сковывая силы противника от района Курска, войска Южного фронта под командованием Толбухина с 17 июля по 2 августа пытались прорвать немецкую оборону на реке Миус, но так и не смогли это сделать.
Тщательно проанализировав действия войск при прорыве обороны, Толбухин через полмесяца снова начал наступательную операцию.
По новому плану основной удар по немецкой обороне наносился в центре полосы силами 2-й гвардейской и 5-й ударной армий. Для развития успеха после прорыва обороны в сражение вводилась конно-механизированная группа, состоящая из 4-го механизированного и 4-го гвардейского кавалерийского корпусов. На направлении главного удара планировалось довести плотность огня до 200 орудий и минометов на один километр фронта. В дальнейшем войска Южного фронта в тесном взаимодействии с войсками Юго-Западного фронта ликвидируют немецкие части на юге Донбасса, развивают наступление на Мелитополь, в направлении Крыма и низовьев Днепра.
