В октябре 1918 года, после объявления мобилизации бывших офицеров, Толбухин был зачислен в Красную армию. Более полугода он прослужил в военкомате, а в июне 1919 года подал прошение об отправке в действующую армию.
Сражался на Западном фронте против белогвардейцев и участвовал в советско-польской войне. За личную храбрость в боях у Новогеоргиевской крепости (в 30 километрах от Варшавы) Толбухин был награжден орденом Красного Знамени.
После окончания Гражданской войны Федор Иванович стал начальником штаба 56-й пехотной дивизии Петроградского военного округа.
В 1934 году он был назначен начальником штаба 1-го стрелкового корпуса, который дислоцировался в Новгороде, затем начальником штаба 19-го стрелкового корпуса, размещавшегося в Ленинграде.
В июне 1938 года Толбухина переводят на должность начальника штаба Закавказского военного округа. Под его руководством работа штаба сильно изменилась. Толбухин лично проверял все важнейшие в военном отношении пограничные районы, состояние дорог, изучал горные перевалы и малодоступные тропы. Большое внимание он уделял организации управления войсками. За успехи в боевой подготовке в конце 1938 года Федору Ивановичу было присвоено звание комдива, а в июне 1941 года — звание генерал-майора.
В первые месяцы Великой Отечественной войны генерал-майор Толбухин назначается начальником штаба Закавказского фронта. Когда советское правительство приняло решение о вводе войск в северные районы Ирана, то благодаря умелой работе штаба, возглавляемого Толбухиным, была обеспечена полная секретность осуществляемых мероприятий.
Немецкие армии стремительно продвигались по советской территории, и уже осенью 1941 года бои развернулись на подступах к Ростову и в Крыму. Зимой 1941/42 года военным советом фронта была спланирована и успешно проведена Керченско-Феодосийская десантная операция — высадка главных сил десанта непосредственно в порту Феодосии прямо с военных кораблей. План был разработан Толбухиным.
В июле 1942 года Толбухин получил назначение на должность командующего 57-й армией Сталинградского фронта. Его армия сыграла важную роль в битве за Сталинград. Соединения Толбухина остановили продвижение немецких частей в районах Абганерово, Плодовитое, Тингута.
В августе 1942 года 4-я танковая немецкая армия генерала Гота, возобновив наступление, обрушила основной удар на 57-ю армию Толбухина. Свыше трех месяцев соединения армии вели тяжелые оборонительные бои. Толбухину удавалось своевременно предугадывать замысел противника, он умело маневрировал резервами, вовремя выдвигая их в направлении главных ударов. В оборонительных боях немцам был причинен значительный урон, и все их попытки прорваться к городу терпели неудачу. На втором этапе сражения за Сталинград армия Толбухина вошла в состав ударной группировки войск Сталинградского фронта.
В развернувшемся 19 ноября контрнаступлении 57-я армия сыграла решающую роль, приняв активное участие в ликвидации 6-й немецкой полевой армии фельдмаршала Паулюса.
За Сталинград Толбухин был отмечен орденом Суворова I степени и очередным званием генерал-лейтенанта, а 28 апреля 1943 года — званием генерал-полковника.
За успешную Донбасскую наступательную операцию советских войск Толбухин был произведен в генералы армии. Это было третье генеральское звание, полученное им менее чем за год.
В апреле 1944 года во время Крымской операции войскам Толбухина предстояло прорвать долговременную оборону противника. Немцы потеряли в Крыму до 100 тысяч человек убитыми и пленными, а также всю боевую технику. Крым был освобожден от немецких частей. Федор Иванович был назначен командующим войсками 3-го Украинского фронта, которым он командовал до самого конца войны.
Одной из наиболее ярких операций, проведенной войсками фронта под командованием Толбухина, стала Ясско-Кишиневская (20–29 августа 1944 года). При разработке плана операции Толбухин предложил нанести главный удар с Кицканского плацдарма южнее города Бендеры. По его замыслу здесь необходимо было сосредоточить основные силы фронта, чтобы достичь решающего превосходства над войсками противника. Затем мощным ударом прорывалась немецкая оборона, и группировка противника «разрывалась» на две части. В прорыв вводились механизированные соединения и, продвигаясь вперед, вступали во взаимодействие с частями 2-го Украинского фронта.
Войска ударной группировки Толбухина окружили и уничтожили немецкую группу армий «Южная Украина» — 22 немецкие дивизии и румынские части. Советские войска расчистили дорогу на Балканы. За искусное проведение операции Указом Президиума Верховного Совета СССР от 12 сентября 1944 года Толбухину было присвоено звание Маршала Советского Союза.
Войска 3-го Украинского фронта за десять дней освободили от немецких войск всю территорию Болгарии. Толбухин был награжден высшим орденом Болгарии «За храбрость».