Реорганизацию Красной Армии Украины на основе указаний ЦК РКП(б) и В. И. Ленина Н. И. Подвойский начал с создания центрального аппарата военного управления. Используя опыт, приобретенный в 1917–1918 годах, он в короткий срок сформировал аппарат Наркомвоена Украины и наладил его работу.

Бескомпромиссно, преодолевая все препятствия (а они были — некоторые местные военные работники настойчиво ратовали за сохранение партизанских методов управления армией и ведения войны), Н. И. Подвойский повел линию на формирование регулярной Красной Армии Украины. Верными единомышленниками и помощниками ему были начальник штаба наркомата М. А. Соков-нин и его заместитель Б. М. Шапошников. Поддерживали его командующий Украинским фронтом В. А. Антонов-Овсеенко, член PBG Е. А. Щаденко, председатель ВВИ Украины В. Г. Юдовский и другие.

Чтобы не заниматься «изобретением велосипеда» и максимально использовать на Украине опыт военного строительства РСФСР, Н. И. Подвойский 15 февраля 1919 года запросил из Москвы 25 комплектов приказов Наркомвоена и Реввоенсовета, 18 февраля — сборник приказов Высшей Военной Инспекции и Положение об окружных военкоматах. Н. И. Подвойский телеграфировал: «Ускорьте высылку, чтобы на месте удержать людей от импровизации». Из Москвы были присланы воинские уставы, инструкции, наставления, программы для обучения войск. Часть необходимых документов в срочном порядке была разработана на месте.

Следующим шагом было формирование военкоматов. Это была далеко не простая задача. Органы Советской власти, создаваемые на местах вслед за наступающим фронтом, были слабы. Селяне, не очень уверенные в окончательном освобождении, не спешили распускать свои партизанские отряды, во главе которых стояли атаманы и батьки всех мастей. Многие из таких отрядов были засорены явными и тайными кулацко-эсеровскими и анархистскими элементами, которые не хотели признавать никакой, кроме своей, власти. Словно на дрожжах, рос бандитизм. Как и в России весной 1918 года, на Украине весной 1919 года не сыскать было места, где бы не было войны.

Создание военкоматов, проведение первых мобилизаций — все это давалось с невероятными трудностями. На стол Н. И. Подвойского то и дело ложились донесения о том, что на тот или другой военкомат налетела «желтая», «зеленая», «черная» или иного цвета банда, посекла военкоматчиков, разогнала, а то и расстреляла призывников, явившихся для вступления в Красную Армию. Невзирая на опасности, почти высохший и охрипший, носился Подвойский, как и его помощники, на автомобилях, тачанках и бронепоездах в этом кипящем котле во губернским и уездным городам, по волостям, помогая проводить мобилизации. Случалось всякое: перестрелки, засады, погони, горькие потери боевых товарищей. Но вселяла уверенность вера: так победим! Помогал опыт революции, которой пошел уже 2-й год, помогал опыт, приобретенный лично Подвойским. Он не раз, разрешая непростые задачи на Украине, вспоминал былое.