Впервые Толбухину удалось познакомиться с Бирюзовым в напряженный период боев под Сталинградом. Их еще не связывали в то время определенные должностные отношения. Толбухин командовал 57-й армией, Бирюзов был в то время начальником штаба 2-й гвардейской армии у Малиновского. Знакомство состоялось на командном пункте Федора Ивановича. Было это в первой половине декабря 1942 года.
Обстоятельства сложились тогда таким образом, что КП Толбухина в хуторе Верхне-Царицынском оказался, вероятно, единственным в своем роде за всю военную историю: здесь под одной крышей расположились тогда сразу два командарма. К тому же армии, которыми они командовали, действовали в диаметрально противоположных направлениях. 57-я Толбухина, повернутая фронтом на восток, участвовала в окончательной ликвидации находившейся в кольце группировки фельдмаршала Паулюса. А 2-я гвардейская Малиновского, спешно переброшенная на реку Мышкова, сначала остановила на этом рубеже войска другого фашистского фельдмаршала - Манштейна, который должен был вызволить из окружения Паулюса, а затем заставила повернуть его вспять и быстро откатываться к Ростову.
Одновременно на КП 57-й армии располагался тогда же и представитель Ставки ВГК Василевский, использовавший имевшийся надежный узел связи для переговоров с командующим Сталинградским и Юго-Западным фронтами. Как говорится, в тесноте, да не в обиде.
Сергей Семенович в ту первую встречу запомнился Толбухину своей солдатской прямотой и искренностью. Он не скрывал признательности и горячо благодарил за помощь и поддержку, которую нашел штаб армии Малиновского на КП Толбухина. 57-я действительно по-братски выручила 2-ю гвардейскую в трудный момент сосредоточения на рубеже реки Мышкова для отпора войскам Манштейна, предоставив в распоряжение ее командования все имевшиеся средства связи. При расставании Бирюзов без всяких околичностей сказал, что многое для себя почерпнул за эти дни совместного пребывания на командном пункте Толбухина и больше всего завидует штабу, который сумел организовать такую отличную связь.
Эти слова не были просто данью вежливости за гостеприимство и помощь. Как убедился затем, уже при совместной работе, Федор Иванович, Бирюзов комплиментов зря не умел раздавать. А уж если подметил у других что-нибудь заслуживающее внимания, то все делал, чтобы у самого было не хуже. Штабное дело он знал досконально. Работу штаба фронта сумел поставить так, что у командующего не возникало сколько-нибудь серьезных претензий. При всем этом в начальнике штаба заметно сказывалась жилка строевого начальника, да он и не скрывал ее. Толбухин не мешал ее проявлению.
Командующий и начальник штаба фронта довольно скоро нашли то деловое и товарищеское взаимопонимание, которое делало их совместную работу наиболее плодотворной. Вероятно, с легкой руки Александра Михайловича Василевского и в Ставке сложилось твердое мнение, что боевое содружество и совместная деятельность Толбухина и Бирюзова во фронтовом руководстве - пример едва ли не идеально удачного сочетания качеств двух военачальников.
Данное обстоятельство, конечно же, учитывала Ставка, назначая их вместе на Третий Украинский фронт. Учитывала она, вероятно, также и то, что оба они, начиная от Волги и кончая наступлением в Крыму, руководили операциями, в которых противостоящие вражеские войска были не однородными, а смешанными.
Последнее предположение оба высказали сразу же после того, как узнали о своем новом назначении. Оба согласились с тем, что оно вполне реально. Обсуждали же они этот вопрос не из праздного любопытства, но единственно ради наилучшего уяснения своего собственного места и роли в новом предстоящем деле. Третьему Украинскому фронту в настоящий момент как раз и противостоит группировка вражеских войск "Думитреску" в составе 6-й немецкой и 3-й румынской армий. Коль скоро их предположение реально, из этого можно было сделать вывод: Ставка и Генеральный штаб считают, что до сих пор они умели использовать подобную неоднородность войск противника и, следовательно, смогут опираться на имеющийся опыт и в будущей операции...
Вывод, как мы видим, весьма немаловажный для уяснения правильного подхода к решению предстоящей задачи. Что касается других выводов, их надлежало сделать в ходе детального изучения обстановки на месте, не теряя ни часа драгоценного времени. Именно поэтому Толбухин и заторопил Бирюзова с отъездом на Третий Украинский. Сам же остался еще на несколько дней в Крыму, чтобы решить ряд организационных вопросов, связанных с отправкой войск Четвертого Украинского фронта на другие направления.
...Полет как начался, так и закончился в прекрасную погоду. Вот уже самолет коснулся поверхности аэродрома, встряхиваясь на неровностях грунта, замедлил свой бег, отвернул с посадочной полосы, подрулил к стоянке, развернулся, в последний раз с нарастающей силой загудев моторами. Затем, стихая до шелеста, остановилось вращение винтов, всякое движение прекратилось. Непривычная тишина на какое-то время оглушила всех сидящих в самолете. Но вот послышались шаги, кто-то открыл кабину и выбросил наружу стремянку. Подошел командир корабля, доложил о завершении полета.
Толбухин поднялся с кресла, поблагодарил экипаж и, не очень твердо ступая затекшими от длительного сидения ногами, направился к выходу. После непрерывного гула и вибрирования летящего самолета, после болтанки и кабинных запахов бензина, перемешанного с горячим маслом, аромат цветущей, залитой солнцем земли за проемом самолетной двери чувствовался с разительной силой. Растянуться бы сейчас на изумрудном травяном ковре да полежать, ни о чем не думая, просто глядя в бездонную синь неба, вбирая в себя теплоту этого солнечного дня, ласковое дуновение ветерка...
Летать Толбухину по служебным делам приходилось довольно часто, человек оп был физически крепкий. И все же не привык к полетам, предпочитая им тряску в машине по любым, пусть разбитым, но земным дорогам. Винтовому самолету того времени, хотя бы и персональному, а значит, с наибольшими возможностями благоустроенному, слишком далеко было до современных реактивных пассажирских лайнеров. Полеты утомляли Федора Ивановича, видно, поэтому он всегда с особенным уважением относился к летчикам, ценя их нелегкий труд и поражаясь их выносливости.