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