На втором этапе сражения за Сталинград армия Толбухина вошла в состав ударной группировки войск Сталинградского фронта.

В развернувшемся 19 ноября контрнаступлении 57-я армия сыграла решающую роль. Прорвав оборону противника, она соединилась 23 ноября в районе хутора Советский с войсками Юго-Западного фронта. В последующем, войдя в состав Донского фронта в январе 1943 года, армия принимала активное участие в ликвидации 6-й немецкой полевой армии фельдмаршала Паулюса.

За Сталинград Толбухин был отмечен орденом Суворова I степени, и ему было присвоено очередное звание генерал-лейтенанта.

После окончания Сталинградской битвы, в марте 1943 года, Толбухин назначается командующим войсками Южного фронта, а 28 апреля ему присваивается звание генерал-полковника.

Первой операцией в должности командующего фронтом для Толбухина стала операция по прорыву обороны противника на реке Миус. Немцы объявили Миус нерушимой границей Германии на востоке. Ее оборона начала создаваться еще в 1941 году и все это время продолжала совершенствоваться. К лету 1943 года оборона достигала в глубину 40—50 километров и состояла из трех полос, на которых располагались минные и проволочные заграждения, мощные доты и дзоты.

Отвлекая и сковывая силы противника от района Курска, войска Южного фронта под командованием Толбухина с 17 июля по 2 августа пытались прорвать немецкую оборону на реке Миус, но так и не смогли это сделать.

Тщательно проанализировав действия войск при прорыве обороны, Толбухин через полмесяца снова начал наступательную операцию.

По новому плану основной удар по немецкой обороне наносился в центре полосы силами 2-й гвардейской и 5-й ударной армий. Для развития успеха после прорыва обороны в сражение вводилась конно-механизированная группа, состоящая из 4-го механизированного и 4-го гвардейского кавалерийского корпусов. На направлении главного удара планировалось довести плотность огня до 200 орудий и минометов на один километр фронта. В дальнейшем войска Южного фронта в тесном взаимодействии с войсками Юго-Западного фронта ликвидируют немецкие части на юге Донбасса, развивают наступление на Мелитополь, в направлении Крыма и низовьев Днепра.

Донбасская наступательная операция советских войск началась 13 августа мощной артиллерийской подготовкой. К 22 сентября 1943 года она завершилась полным успехом. Федор Иванович Толбухин за успешные действия войск был произведен в генералы армии. Это стало третьим генеральским званием, полученным им менее чем за год.

Затем последовал ряд других успешных наступательных операций. В результате Мелитопольской наступательной операции (26 сентября – 5 ноября 1943 года) Южный фронт, который с 20 октября был переименован в 4-й Украинский фронт, блокировал противника в Крыму и вышел к Днепру в его нижнем течении. Войска 51-й армии при взаимодействии с 28-й армией к 13 октября сумели овладеть южной частью Мелитополя, а к 23 октября взят был и весь город. С 26 октября немецкие войска были вынуждены начать общее отступление. В ходе этой операции войсками 4-го Украинского фронта было полностью разгромлено 8 дивизий противника, и еще 12 дивизий понесли большие потери. Была почти полностью очищена от неприятеля Северная Таврия и с суши блокирована немецкая группировка в Крыму. За Мелитопольскую операцию Толбухин был награжден орденом Ленина.

Зимой (30 января – 29 февраля) 1944 года войска 4-го Украинского фронта при взаимодействии с 3-м Украинским фронтом ликвидировали немецкий плацдарм на левом берегу Днепра, в районе Никополя. В ходе этой операции были освобождены важные промышленные центры юга Украины – Кривой Рог и Никополь.