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