Если с явными врагами бороться было сравнительно просто, то с тайными дело обстояло по-иному. Они тщательно маскировались, принимали личину друзей, так что распознать и обезвредить их было не так-то просто. Уже на третий день прибытия Бирюзова в Софию ему позвонил главнокомандующий болгарской армии И. Маринов. Генерал срочно просил совета, как ему поступить. Дело состояло в том, что в этот день к Маринову явилась группа английских и американских офицеров и потребовала выделить в распоряжение союзников аэродром, показать планы минных полей на Черноморском побережье и предоставить им порт на Черном море, на юге страны, куда в ближайшее время должны прибыть английские корабли. Для подготовки к приему кораблей, сообщили незваные визитеры, в Болгарию уже высланы офицер и инженер. Они предложили также военную помощь союзников Болгарии, хотя ни болгарское правительство, ни советское командование не просили их об этом.
Маринов уклонился от ответа и теперь, взволнованный, опасаясь обострения обстановки, звонил Бирюзову. Тот успокоил его и заверил, что ничего особенного произойти не может, поскольку в Болгарии стоят войска целого советского фронта, но посоветовал при следующей встрече, назначенной на другой день, сообщить союзникам, что без согласования с советским командованием болгары не смогут выполнить какие-либо требования. При следующей встрече присутствовали и советские представители. Они заявили, что «надобности в союзниках не имеется».
Казалось бы (с точки зрения Бирюзова, человека военного), ответ был дан четкий и ясный, однако неопытность в дипломатических делах стоила генерал-полковнику неприятностей. Когда ответ советских представителей союзникам был доложен в Москву министру иностранных дел В. М. Молотову, тот на углу телеграммы написал:
«Не следует говорить, что в союзниках «надобности не имеется». Надо сказать, чтобы союзники предварительно согласовывали такие вопросы в Москве, а в Болгарии не вступать с ними в переговоры, а вежливо указывать — договоритесь с Москвой».
Бирюзову сообщили об этом, и он понял: надо учиться дипломатии. Теперь, когда 3-й Украинский фронт перешагнул границы СССР, видимо, не раз придется участвовать в решении дипломатических вопросов. Но и на этом происшествие не закончилось. Молотов рассказал об этом И. В. Сталину, а тот при очередном докладе заместителя начальника Генштаба генерала А. И. Антонова заметил ему, что военные должны знать основы международного права, а затем, подумав, добавил: «Речь идет о военных, которые сами ведут переговоры с иностранцами или участвуют в переговорах, разрабатывают важные военно-дипломатические документы. Вот они-то и должны знать, как это нужно правильно делать, чтобы достойно представлять нашу страну». Упрек был справедлив, и советские военачальники в последние месяцы войны много и плодотворно учились у дипломатов. Бирюзов, как и другие, учился военно-дипломатическому искусству настойчиво и успешно.
В дальнейшем английские и американские представители не раз еще пытались оказать влияние на болгарские дела. Некоторые из них прямо вели разведку советских войск в Болгарии. Таких пришлось вежливо (сказались уроки дипломатии) выдворить из страны. Тогда началась разведка болгарских войск в Греции, попытки поставить под англо-американский контроль освобожденные греческие территории. Выяснилось, что военный министр Велчев, а также высший чиновничий аппарат Болгарии поддерживают англо-американские домогательства. При встречах же с советскими представителями Велчев возражал против отправки болгарских войск на фронт, ссылаясь на их небоеспособность. Бирюзов сумел быстро разглядеть истинную позицию болгарского военного министра. Он так повел дело, что болгарская армия с помощью болгарских патриотов в кратчайший срок была очищена от контрреволюционных и профашистских элементов и плечом к плечу с войсками 3-го Украинского фронта мужественно сражалась против гитлеровского вермахта, чем внесла свой вклад в общую победу над врагом.
При всех своих новых ответственных военно-дипломатических обязанностях Бирюзов оставался и начальником штаба фронта. А перед его войсками встала важная задача — 3-й Украинский фронт готовился к освобождению Югославии, и прежде всего ее столицы Белграда. Надо было спланировать эту крупную операцию, делать массу дел, но сроки подготовки по ее обеспечению, как всегда, были жесткими. Директиву Ставки о подготовке Белградской операции получили 20 сентября, а уже через неделю предписывалось начать наступление. Но чтобы сосредоточить войска на болгаро-югославской границе для нового удара, надо было собрать воедино разбросанные на большом пространстве соединения, некоторым из них предстоял марш по 600 километров в условиях горных дорог, что уже само по себе непросто. Цель операции состояла в том, чтобы совместными усилиями советских, югославских и болгарских войск разгромить вражескую армейскую группу «Сербия», оборонявшуюся в восточной части Югославии, освободить Сербию и Белград и выйти на коммуникации группы армий «Е», находившейся в Греции, и отрезать ей отход на юг Балканского полуострова. Новым моментом было то, что в отличие от всех прошлых операций в этой вместе с 3-м Украинским фронтом действовали шесть югославских корпусов и три болгарские армии, с которыми надо было установить взаимодействие и поставить задачи, способствовавшие достижению общей цели.
Дело осложнялось тем, что в недалеком прошлом монархо-фашистское правительство Болгарии предоставило в распоряжение германского командования экспедиционный корпус, который выполнял в Югославии жандармские функции. Поэтому теперь, когда югославским и болгарским войскам предстояло действовать в едином строю, требовалась огромная разъяснительная работа среди югославских войск и населения, чтобы правильно было понято участие болгар в Белградской операции. Ставка Верховного Главнокомандования, очевидно, высоко оценивая военно-дипломатическую деятельность Бирюзова в Болгарии, поручила ему встретиться с главнокомандующим Народно-освободительной армии Югославии (НОАЮ) маршалом Иосипом Броз Тито, а также организовать переговоры югославских представителей с болгарами и решить все вопросы взаимодействия трех братских армий в предстоящем наступлении в Сербии.
Бирюзов прибыл в румынский город Крайову, где была назначена встреча, 5 октября и в тот же день встретился с Тито. Туда же прибыла и болгарская делегация. Маршал одобрил доложенный Бирюзовым план операции. С большим пониманием отнеслись югославы к участию войск новой, демократической Болгарии в освобождении Югославии. Все присутствующие сошлись на том, что, как писал Бирюзов, «болгарский народ не может носить на себе клеймо Каина за преступные действия бывшего царского правительства». В ходе дальнейших переговоров, состоявшихся в тот же день, югославские и болгарские представители решили весь круг вопросов, связанных с взаимодействием их вооруженных сил. К вечеру уже было подписано соглашение о военном сотрудничестве в борьбе против общего врага, а затем состоялся товарищеский ужин, где царил дух братской дружбы.
Во время проведения Белградской операции Бирюзов, как обычно, находился большей частью в гуще наступавших на Белград войск. Тринадцатого октября советские танкисты 4-го гвардейского мехкорпуса вместе с югославскими частями овладели горой Авала, господствующей высотой в 15 километрах от Белграда. Захват этой горы, кроме ее тактического значения, имел для югославов значение символическое. Она была овеяна легендами о славных подвигах лучших сынов Сербии, здесь находилась могила Неизвестного солдата, всегда украшенная цветами. Бирюзов с пониманием и сочувствием смотрел на югославских воинов, ликовавших в связи с освобождением национальной святыни.
Часто бывал Бирюзов в те дни и в болгарских войсках. Несмотря на трудные условия боев в лесистых горах, болгары воевали хорошо. Однажды он наблюдал штыковую атаку болгарской пехоты. В темных шинелях и лихо смятых фуражках, напоминавших форму русской царской армии, болгарские воины безудержным рывком заставили замолчать пулеметы противника, ворвались в его окопы. «По-русски дерутся!» — сказал кто-то из спутников Бирюзова. И Бирюзову было это приятно. Как-никак он после своей совместной работы в Болгарии чувствовал моральную ответственность за ее армию. И практическое подтверждение того, что болгары молодцы, что воевать умеют, что горят желанием бить врага, приносило чувство удовлетворения».