В тот же день Н. И. Подвойский встретился и побеседовал со многими членами ЦК КП(б)У и правительства — Артемом (Ф. А. Сергеевым), В. П. Затонским, К. Е. Ворошиловым, В. И. Межлауком, X. Г. Раковским, командующим Украинским фронтом В. А. Антоновым-Овсеенко и другими. Многих он знал ранее, некоторых увидел впервые. Встречи с руководителями не были простой формальностью. Н. И. Подвойский в беседах и при знакомстве с важнейшими документами получал необходимую ему информацию. Тут же анализировал ее, чтобы уяснить обстановку, в которой придется работать. Ему стало известно, что Советская власть, устанавливаемая прямо за движением Украинского фронта, существует пока только в Харьковской, Екатеринославской, Полтавской и Черниговской губерниях. В Красной Армии Украины преобладают отрядность и партизанщина. Это было обусловлено, с одной стороны, условиями борьбы то против оккупантов, то гетмановцев, то петлюровцев, то против иных контрреволюционных местных властей, а с другой стороны — влиянием сторонников партизанщины эсеров, идеи которых попадали здесь на благодатную почву — более многочисленное, чем в России, кулачество и довольно мощный слой среднего крестьянства, мечущегося между сельской буржуазией и пролетариатом.
Поразмыслив, Н. И. Подвойский пришел к выводу, что положение на Украине, в военном строительстве особенно, очень похоже на обстановку в РСФСР начала 1918 года, когда еще только устанавливалась и укреплялась Советская власть и делались первые шаги по созданию Красной Армии. Исходя из этого, он определил следующую программу работы: «1) Организовать стройную систему военного управления… 2) Организовать регулярную Красную Армию… тактически обученную… дисциплинированную, самоотверженную, хорошо управляемую при посредстве отобранных Советской властью командиров. 3) Подготовить красный командный состав непосредственно из рабочей и крестьянской массы. Организовать планомерное снабжение Красной Армии, освобождая население от поборов и реквизиций… 4) Подготовка всех трудящихся при помощи всеобщего военного обучения… к выполнению своей обязанности защищать свое социалистическое отечество…»
Реорганизацию Красной Армии Украины на основе указаний ЦК РКП(б) и В. И. Ленина Н. И. Подвойский начал с создания центрального аппарата военного управления. Используя опыт, приобретенный в 1917–1918 годах, он в короткий срок сформировал аппарат Наркомвоена Украины и наладил его работу.
Бескомпромиссно, преодолевая все препятствия (а они были — некоторые местные военные работники настойчиво ратовали за сохранение партизанских методов управления армией и ведения войны), Н. И. Подвойский повел линию на формирование регулярной Красной Армии Украины. Верными единомышленниками и помощниками ему были начальник штаба наркомата М. А. Соков-нин и его заместитель Б. М. Шапошников. Поддерживали его командующий Украинским фронтом В. А. Антонов-Овсеенко, член PBG Е. А. Щаденко, председатель ВВИ Украины В. Г. Юдовский и другие.
Чтобы не заниматься «изобретением велосипеда» и максимально использовать на Украине опыт военного строительства РСФСР, Н. И. Подвойский 15 февраля 1919 года запросил из Москвы 25 комплектов приказов Наркомвоена и Реввоенсовета, 18 февраля — сборник приказов Высшей Военной Инспекции и Положение об окружных военкоматах. Н. И. Подвойский телеграфировал: «Ускорьте высылку, чтобы на месте удержать людей от импровизации». Из Москвы были присланы воинские уставы, инструкции, наставления, программы для обучения войск. Часть необходимых документов в срочном порядке была разработана на месте.
Следующим шагом было формирование военкоматов. Это была далеко не простая задача. Органы Советской власти, создаваемые на местах вслед за наступающим фронтом, были слабы. Селяне, не очень уверенные в окончательном освобождении, не спешили распускать свои партизанские отряды, во главе которых стояли атаманы и батьки всех мастей. Многие из таких отрядов были засорены явными и тайными кулацко-эсеровскими и анархистскими элементами, которые не хотели признавать никакой, кроме своей, власти. Словно на дрожжах, рос бандитизм. Как и в России весной 1918 года, на Украине весной 1919 года не сыскать было места, где бы не было войны.