В первые месяцы Великой Отечественной войны генерал-майор Толбухин назначается начальником штаба Закавказского фронта. Когда советское правительство приняло решение о вводе войск в северные районы Ирана, то благодаря умелой работе штаба, возглавляемого Толбухиным, была обеспечена полная скрытность осуществляемых мероприятий. Тщательно подготовленная операция была проведена внезапно для сопредельной стороны и без существенных потерь.
Немецкие армии стремительно продвигались по советской территории, и уже осенью 1941 года бои развернулись на подступах к Ростову и в Крыму. В конце года военным советом фронта была спланирована Керченско-Феодосийская десантная операция. В ее замысел входила высадка главных сил десанта непосредственно в порту Феодосии прямо с военных кораблей. План операции был разработан под руководством Толбухина, а сама операция прошла в период с 25 декабря 1941 по 2 января 1942 года и закончилась полным успехом.
В конце января 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 орудий и минометов на один километр фронта. В дальнейшем войска Южного фронта в тесном взаимодействии с войсками Юго-Западного фронта ликвидируют немецкие части на юге Донбасса, развивают наступление на Мелитополь, в направлении Крыма и низовьев Днепра.
Донбасская наступательная операция советских войск началась 13 августа мощной артиллерийской подготовкой. К 22 сентября 1943 года она завершилась полным успехом. Федор Иванович Толбухин за успешные действия войск был произведен в генералы армии. Это стало третьим генеральским званием, полученным им менее чем за год.
Затем последовал ряд других успешных наступательных операций. В результате Мелитопольской наступательной операции (26 сентября – 5 ноября 1943 года) Южный фронт, который с 20 октября был переименован в 4-й Украинский фронт, блокировал противника в Крыму и вышел к Днепру в его нижнем течении. Войска 51-й армии при взаимодействии с 28-й армией к 13 октября сумели овладеть южной частью Мелитополя, а к 23 октября взят был и весь город. С 26 октября немецкие войска были вынуждены начать общее отступление. В ходе этой операции войсками 4-го Украинского фронта было полностью разгромлено 8 дивизий противника, и еще 12 дивизий понесли большие потери. Была почти полностью очищена от неприятеля Северная Таврия и с суши блокирована немецкая группировка в Крыму. За Мелитопольскую операцию Толбухин был награжден орденом Ленина.
Зимой (30 января – 29 февраля) 1944 года войска 4-го Украинского фронта при взаимодействии с 3-м Украинским фронтом ликвидировали немецкий плацдарм на левом берегу Днепра, в районе Никополя. В ходе этой операции были освобождены важные промышленные центры юга Украины – Кривой Рог и Никополь.
8 апреля 1944 года началась Крымская операция. Для ее проведения в район Крыма была переброшена 2-я гвардейская армия и сосредоточены большие силы артиллерии и бронетанковых войск. Войскам предстояло прорвать долговременную оборону противника, глубина которой составляла 35—40 километров. Операцию планировалось провести силами 4-го Украинского фронта, Отдельной Приморской армии при содействии Черноморского флота. План предусматривал нанесение одновременных ударов с севера и востока в общем направлении на Керчь. В течение пяти дней до начала операции артиллерия проводила мощный обстрел вражеских укреплений, а началу атаки предшествовала двухчасовая артиллерийская и авиационная подготовка. Основная роль в проведении операции отводилась 4-му Украинскому фронту.
После кровопролитных боев 51-я армия, наступавшая с сивашского плацдарма, уже 10 апреля сумела прорвать оборону противника. В прорыв Толбухин сразу же вводит 19-й танковый корпус, который на следующий день занимает Джанкой – важный стратегический пункт немецкой обороны. Опасаясь окружения, немецкое командование отводит войска на юг Крыма и с Керченского полуострова, где наступала Приморская армия. Войска под командованием Толбухина, прорвав оборону 11-й немецкой армии на крымских перешейках, устремились к Севастополю и 9 мая освободили город. Чуть больше месяца понадобилось советским войскам, чтобы разгромить две немецкие армии, и к 12 мая весь Крым был освобожден от немецких частей. Немцы потеряли в Крыму до 100 тысяч человек убитыми и пленными и всю боевую технику.
После окончания Крымской операции Федор Иванович был назначен командующим войсками 3-го Украинского фронта, которым он командовал до самого конца войны.
Одной из наиболее ярких операций, проведенной войсками фронта под командованием Толбухина, стала Ясско-Кишиневская (20—29 августа 1944 года). При разработке плана операции Толбухин предложил нанести главный удар с Кицканского плацдарма южнее города Бендеры. При успешном развитии наступления отсюда был самый короткий путь на соединение с войсками 2-го Украинского фронта. К тому же немцы вряд ли смогли бы предположить, что советское командование начнет наступление с такого крошечного плацдарма (всего 18 километров).