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