В течение второй половины сентября в Генштабе, в штабе 3-го Украинского фронта, в Верховном штабе НОАЮ, в главном штабе Сербии работали над планом Белградской операции. Должен отметить очень большую целеустремленность и слаженность этой работы, хотя она проводилась разными национальными штабами и проходила в местах, удаленных друг от друга на многие сотни, а иногда и тысячи километров. Достигалась эта целеустремленность в значительной мере благодаря большой активности А. И. Антонова и Н. В. Корнеева. Они отлично знали и понимали друг друга еще с Академии Генерального штаба (учились вместе). Как только Корнеев получил возможность связываться из Крайовы по ВЧ непосредственно с советским Генштабом, он не замедлил этим воспользоваться. Алексей Иннокентьевич изложил начальнику военной миссии суть соображений Генштаба по разгрому противника под Белградом и попросил его согласовать их с Верховным штабом НОАЮ, что и было сделано. Верховный штаб с одобрением отнесся к мнению советского Генштаба и передал необходимые распоряжения командующему 1-й армейской группой генерал-подполковнику Пеко Дапчевичу, который со своим штабом работал над планом действий под Белградом войск НОАЮ.
30 сентября командование 3-го Украинского фронта доложило в Генеральный штаб свои соображения, тоже согласованные заранее с руководством НОАЮ. Цель совместной советско-югославской операции состояла в том, чтобы ликвидировать группировку войск противника в северо-восточной Югославии, захватить важнейшие узлы дорог, отрезать врагу пути отхода из центральной и южной части Югославии на север в Венгрию и, наконец, освободить Белград.
Для решения этих задач 3-й Украинский фронт выделял 57-ю армию генерала Н. А. Гагена и 4-й гвардейский механизированный корпус под командованием генерала В. И. Жданова. С воздуха операция обеспечивалась силами 17-й воздушной армии.
Нашим войскам непосредственно противостояла гитлеровская армейская группа "Сербия", которая имела в первой линии до четырех дивизий, в том числе одну моторизованную. В ходе операции предполагался подход еще двух дивизий из района Ниша и некоторых сил из состава греческой группировки войск противника. Штаб Ф. И. Толбухина допускал возможность сосредоточения в полосе наступления 57-й армии до десяти-одиннадцати дивизий врага. Поэтому Военный совет 3-го Украинского фронта высказывал пожелания, чтобы НОАЮ оттянула на себя часть немецко-фашистских войск и преградила им путь на север, связала войска фашистских прихвостней Недича и Михайловича южнее и юго-западнее Белграда. При возможности югославским войскам предлагалось захватить Ниш. Все эти соображения были переданы через Н. В. Корнеева в Верховный штаб НОАЮ, который поставил задачи своим войскам.
Планы Ф. И. Толбухина относительно наступления на Белград опирались на точнее знание реальной обстановки. Он учитывал, что войска 57-й армии прочно закрепились на правом берегу Дуная в районе болгарского города Видин и день и ночь готовились к новому броску вперед. Севернее Видина в излучине Дуная успешно завершил тяжелые оборонительные бои 75-й стрелковый корпус, отбив все попытки врага отбросить его назад. Теперь это соединение передали из 2-го Украинского фронта в состав 57-й армии.
Поскольку горная местность не допускала сведения советских войск в единый кулак и вынуждала наступать по направлениям, Ф. И. Толбухин предложил весьма своеобразное решение: иметь главные силы (64-й стрелковой и 4-й механизированный корпуса со средствами усиления) на левом крыле армии в районе Видина для удара в направлении Заечар, Болевац, Чуприя, Баточина, зап. Паланка. Войска должны были разгромить основную группировку сил армейской группы "Сербия" и отсечь ее остаткам путь отхода к Белграду. Одновременно другие советские войска наступали бы вдоль Дуная на Белград (75 ск) и в центре фронта (68 ск) - в направлении Слатина, Жагубица, Златово. На случай задержки наступления на одном из направлений предусматривалась взаимная помощь корпусов. С выходом войск на Мораву и после ее форсирования возникала возможность повернуть основные наши силы непосредственно на Белград, взятием которого завершалась операция. На этом этапе операции наши войска должны были наступать плечом к плечу с войсками НОАЮ. Что касалось войск Болгарии, то Ф. И. Толбухин предусмотрел для них задачу связать противника перед своим фронтом.
Генеральный штаб принял во внимание соображения Военного совета 3-го Украинского фронта как, в основном, правильные. Однако Генштаб считал необходимым привлечь к операции еще и 10-й гвардейский стрелковый корпус 46-й армии 2-го Украинского фронта. Командовал им генерал Иван Андреевич Рубанюк. Войска корпуса могли бы нанести поражение противнику в районе Врашаца и подорвать устойчивость вражеской обороны севернее и восточное Белграда. Не согласились с Толбухиным и в отношении болгарских войск. Поскольку было известно, что главком Болгарии считал возможным наступать, то и Генеральный штаб, докладывая план действий на Белград в Ставке, предложил не ограничивать задачи болгарской армии обороной, а предусмотреть ее наступление.
Ставка согласилась с Генштабом, но в отношении болгарской армии предложила не форсировать событий, пока не будет достигнута всесторонняя и полная договоренность с болгарским и югославским командованием. Толбухину же приказали начать наступление 13-14 октября, когда должно было закончиться сосредоточение войск, участвующих в операции. Любая затяжка сроков давала бы противнику время для подвода в район Белграда новых сил и укрепления обороны. В директиве Ставки, посланной командующему 3-м Украинским фронтом, говорилось: "Свяжитесь с Тито в Крайове и ознакомьте его подробно с планом операции". Толбухин сделал это немедленно, и в течение ночи на 2 октября товарищи из Верховного штаба НОАЮ работали над планом операций. Утром Генеральный штаб в Москве получил донесение, излагавшее решение маршала Тито. Оно предусматривало прежде всего сковать противника южнее и юго-западнее Белграда, не дать врагу перебросить отсюда силы против советских войск, для чего выделялись два армейских корпуса НОАЮ - 12-й и 1-й. После того как противнику будет нанесено поражение, основная масса югославских войск должна была направиться непосредственно против группировки противника в Белграде, а частью сил повернуть на восток, чтобы содействовать войскам Красной Армии, наступавшим из района Неготина.
Захват города Ниш, важного узла железных и шоссейных дорог, возлагался на войска, подчиненные главному штабу Сербии в составе четырех дивизий. Командующий этими войсками генерал-подполковник Коча Попович вызывался для получения задачи в Крайову на 2-3 октября. Маршал Тито в свою очередь просил советское командование предусмотреть удары 3-го Украинского фронта с целью соединения с частями НОАЮ, чтобы совместными усилиями отрезать противника, выдвигавшегося в район Белграда с юга.
Для решения вопроса о наступлении войск новой Болгарии на территории Югославии и для увязки взаимодействия мы привлекли командование 3-го Украинского фронта. Позвонили Ф. И. Толбухину, объяснили деликатность и характер задачи. Федор Иванович предложил поручить столь ответственное дело С. С. Бирюзову, теперь командующему 37-й армией, которая располагалась в районе Софии. Сергей Семенович одновременно являлся и главой Союзной контрольной комиссии в Болгарии. 4 октября С. С. Бирюзов явился в Крайову для встречи с маршалом Тито. Одновременно туда же прибыла болгарская делегация.
С. С. Бирюзов посетил И. Броз Тито дважды. В первый раз он изложил наши предложения по плану Белградской операции. План был принят югославским командованием с большим удовлетворением. В составе советских войск кроме пехоты имелось 2200 орудий и минометов, 149 реактивных установок, 358 танков и самоходно-артиллерийских установок, 1292 самолета, а в Дунайской флотилии почти 80 боевых кораблей (в основном бронекатеров). Об увязке совместных действий 3-го Украинского фронта и войск Народно-освободительной армии договорились быстро.