В дальнейшем Ф. И. Толбухин оставался на должности начальника штаба Закавказского фронта, преобразованного в декабре 1941 года в Кавказский фронт, а в январе — марте выделившегося из Кавказского фронта Крымского фронта. Войска фронта во взаимодействии с Черноморским флотом и Азовской флотилией с 25 декабря 1941 г. по 2 января 1942 г. провели крупную десантную операцию с целью овладения Керченским полуостровом и создания условий для освобождения Крыма. Замысел операции предусматривал одновременную высадку войск в районы Керчи и Феодосии, окружение и уничтожение группировки противника.
Толбухин внес большой вклад в планирование, организацию и обеспечение этой сложнейшей операции, в осуществление взаимодействия с силами флота и авиации, в управление войсками в ходе операции. К исходу 2 января 1942 г. войска Кавказского фронта очистили от врага Керченский полуостров. Это позволило отвлечь часть сил противника от Севастополя, предотвратить вторжение немецко-фашистских войск на Кавказ через Таманский полуостров, овладеть важным оперативным плацдармом в Крыму. По словам одного из ведущих военных теоретиков современной России генерала армии М. А. Гареева, «вследствие недостаточности твердости командующего фронтом Д. Т. Козлова, произвола и некомпетентного вмешательства представителя Ставки ВГК Л. 3. Мехлиса, управление войсками фронта было дезорганизовано. Мехлис, охаивая командование и штаб фронта, обратился к Сталину с просьбой прислать в Крым кого-либо из генералов типа Гинденбурга, не понимая того, что Гинденбург или Жуков, прибыв на этот фронт, первым делом потребовали бы убрать всякого рода мехлисов. Попытки Толбухина придать хоть какую-то плановость и организованность работе командования и штаба фронта привели к обострению отношений со своенравным Мехлисом. В результате Толбухин в марте 1942 г. был отстранен от должности и назначен заместителем командующего Сталинградским военным округом. Как и следовало ожидать, нарушение единоначалия и ряд других ошибок оперативного характера привели в мае 1942 г. войска Крымского фронта к страшной катастрофе».
С мая 1942 г. по февраль 1943 г. Ф. И. Толбухин участвовал в Сталинградской эпопее — весной 1942 г. в должности заместителя командующего войсками Сталинградского военного округа, а с июля 1942 года в должности командующего 57-й армией, которая остановила на южных подступах к Сталинграду 4-ю танковую армию вермахта, повернутую немцами с Кавказского на Сталинградское направление. Обеспечивая глубокое оперативное построение войск с высокой противотанковой устойчивостью, Ф. И. Толбухин стремился, несмотря на острый недостаток сил и средств, иметь в глубине сильные резервы, оснащенные противотанковыми средствами, с тем, чтобы быстро ликвидировать возможные прорывы противника. После тяжелейших оборонительных боев силы армии были сохранены, и с началом общего контрнаступления под Сталинградом 57-я армия успешно выполнила задачи по окружению, расчленению и уничтожению группировки противника. Способность к критической оценке собственных решений и действий, анализу приобретенного опыта и стремление к совершенствованию своего полководческого искусства и боевого мастерства подчиненных командиров не подвели Толбухина и на этот раз. И. В. Сталин высоко оценил таланты опытного войсководца: в январе 1943 г. Ф. И. Толбухину было присвоено звание генерал-лейтенанта, а к сентябрю того же года он стал уже генералом армии.