Дело осложнялось тем, что в недалеком прошлом монархо-фашистское правительство Болгарии предоставило в распоряжение германского командования экспедиционный корпус, который выполнял в Югославии жандармские функции. Поэтому теперь, когда югославским и болгарским войскам предстояло действовать в едином строю, требовалась огромная разъяснительная работа среди югославских войск и населения, чтобы правильно было понято участие болгар в Белградской операции. Ставка Верховного Главнокомандования, очевидно, высоко оценивая военно-дипломатическую деятельность Бирюзова в Болгарии, поручила ему встретиться с главнокомандующим Народно-освободительной армии Югославии (НОАЮ) маршалом Иосипом Броз Тито, а также организовать переговоры югославских представителей с болгарами и решить все вопросы взаимодействия трех братских армий в предстоящем наступлении в Сербии.
Бирюзов прибыл в румынский город Крайову, где была назначена встреча, 5 октября и в тот же день встретился с Тито. Туда же прибыла и болгарская делегация. Маршал одобрил доложенный Бирюзовым план операции. С большим пониманием отнеслись югославы к участию войск новой, демократической Болгарии в освобождении Югославии. Все присутствующие сошлись на том, что, как писал Бирюзов, "болгарский народ не может носить на себе клеймо Каина за преступные действия бывшего царского правительства". В ходе дальнейших переговоров, состоявшихся в тот же день, югославские и болгарские представители решили весь круг вопросов, связанных с взаимодействием их вооруженных сил. К вечеру уже было подписано соглашение о военном сотрудничестве в борьбе против общего врага, а затем состоялся товарищеский ужин, где царил дух братской дружбы.
Во время проведения Белградской операции Бирюзов, как обычно, находился большей частью в гуще наступавших на Белград войск. Тринадцатого октября советские танкисты 4-го гвардейского мехкорпуса вместе с югославскими частями овладели горой Авала, господствующей высотой в 15 километрах от Белграда. Захват этой горы, кроме ее тактического значения, имел для югославов значение символическое. Она была овеяна легендами о славных подвигах лучших сынов Сербии, здесь находилась могила Неизвестного солдата, всегда украшенная цветами. Бирюзов с пониманием и сочувствием смотрел на югославских воинов, ликовавших в связи с освобождением национальной святыни.
Часто бывал Бирюзов в те дни и в болгарских войсках. Несмотря на трудные условия боев в лесистых горах, болгары воевали хорошо. Однажды он наблюдал штыковую атаку болгарской пехоты. В темных шинелях и лихо смятых фуражках, напоминавших форму русской царской армии, болгарские воины безудержным рывком заставили замолчать пулеметы противника, ворвались в его окопы. "По-русски дерутся!" - сказал кто-то из спутников Бирюзова. И Бирюзову было это приятно. Как-никак он после своей совместной работы в Болгарии чувствовал моральную ответственность за ее армию. И практическое подтверждение того, что болгары молодцы, что воевать умеют, что горят желанием бить врага, приносило чувство удовлетворения".
Штурм Белграда был назначен на 14 октября. По поручению Толбухина Бирюзов накануне выехал в войска, чтобы на месте проконтролировать готовность частей и внести необходимые коррективы в их действия.
Взятие югославской столицы проводилось без мощных авиационных и артиллерийских ударов: наступавшие стремились сохранить город от разрушений и нанести возможно меньший ущерб населению. "Русские герои, - писал в 1946 году журнал "Югославия - СССР" (No 4), - проливали свою кровь и за то, чтобы в борьбе при освобождении города как можно меньше погибло детей и женщин. Жители Белграда все это понимали и просто боготворили своих освободителей".
Но это понимал и враг. И защищался ожесточенно, заминировав весь город. Семь дней советские и югославские воины штурмовали город, 20 октября он был полностью освобожден. На следующий день, проезжая по ликующему Белграду, Бирюзов уже думал о новых предстоящих операциях, о неотложных задачах штаба фронта. Но дальше воевать ему не пришлось. Судьба уготовила для него неожиданное. 31 октября Ф. И. Толбухин, возвратившийся из кратковременной поездки в Москву, после первых приветствий сказал встречавшему его Бирюзову: "Назначаетесь командующим 37-й армией, но..." И замолк, нарочито затягивая паузу и испытующе глядя на своего начштаба, "Не томите душу, Федор Иванович!" - взмолился Бирюзов. "На вас возлагается еще одна весьма ответственная обязанность, - продолжал маршал, - вы должны возглавить Союзную контрольную комиссию в Болгарии, Правда, официально председателем СКК назначен я. Однако в Кремле прямо сказали: Бирюзов - ваш заместитель, и все руководство союзническим органом должно находиться в его руках".
