Командирами был замечен храбрый красноармеец, которого так интересовало все связанное с военным делом, и его отправляют учиться в Харьков. В 1922 г. Москаленко заканчивает артиллерийское отделение Объединенной школы червонных старшин, и с этого времени начинается его путь кадрового военного.
Выпускник школы червонных старшин служит в Северо-Кавказском и Белорусском военном округах и занимает все более высокие должности – командира взвода, батареи, дивизиона, начальника штаба артиллерийского полка.
В 1928 г. Москаленко заканчивает артиллерийские курсы усовершенствования командного состава РККА и, показав незаурядные способности командира-артиллериста, продолжает быстро продвигаться по служебной лестнице. В 1934 г. он уже командир артиллерийского полка, в следующем году назначается начальником артиллерии 23-й механизированной бригады на Дальнем Востоке, а в сентябре 1936 г. – 133-й механизированной бригады Киевского военного округа.
Командование в аттестации следующим образом характеризует Москаленко: «…волевой, энергичный, инициативен, решительный и настойчивый в проведении своих решений в жизнь». Одновременно подчеркивается, что должность начальника артиллерии его «тяготит» и аттестуемый «стремится перейти на командную работу». Последнее было абсолютно правильно – Москаленко всегда стремился именно к самостоятельной командной должности, на которой он мог полнее всего реализовать свои способности.
После окончания в 1939 г. факультета усовершенствования высшего командного состава Военной академии имени Ф. Э. Дзержинского, Москаленко назначается начальником артиллерии 51-й Перекопской стрелковой дивизии, дислоцированной в Одессе.
Дивизия в январе 1940 г. перебрасывается из Одессы на Карельский перешеек и принимает участие в военных действиях против Финляндии. Действия дивизии (в которых значительную роль играла прекрасно подготовленная дивизионная артиллерия) были неизменно успешными. 23 февраля дивизия (после проведенной артиллерийской подготовки она успешно наступала на северной стороне станции Кямяря) через два дня овладела важным пунктом финской обороны Хямяля и продолжила дальнейшее наступление.
За войну с Финляндией Москаленко в апреле получает свою первую боевую награду – орден Боевого Красного знамени. После окончания этой «незнаменитой» войны происходит и его очередное повышение – Москаленко становится начальником артиллерии сначала 35-го стрелкового (в составе которого принимает участие в походе в Бессарабию), а потом 2-го механизированного корпуса Одесского военного округа. В апреле 1941 г. осуществляется давняя мечта Москаленко (получившего в январе звание генерал-майора артиллерии) о получении самостоятельной командной должности – он назначается командиром 1-й моторизованной противотанковой артиллерийской бригады, которая в составе 5-й армии формировалась в Луцке.
Командуя бригадой, Москаленко участвует в приграничном сражении, и уже его первый бой стал успешным, благодаря новаторским приемам комбрига. Генералом был тогда применен такой, крайне сложный и рискованный маневр, как встречный артиллерийский бой, и именно в нем 22 июня бригадой были отброшены отборные немецкие танковые подразделения и захвачены первые пленные гитлеровцы (возможно, даже первые для всей РККА).
Приведем описание этой, такой нетипичной для первого дня войны, победы наших войск, сделанное самим Москаленко. Показательно, что он выделяет не собственную роль, а мужество своих солдат: «6-я армия и 1-я танковая группа составляли основные силы группы армий «Юг» (в нее входила также 17-я немецкая армия), развернутые от Влодавы до Крыстынополя, т. е. против 5-й армии и правого фланга нашей 6-й армии. Группировка немцев состояла из пяти танковых, четырех моторизованных и двенадцати пехотных дивизий. В первый день в наступление было брошено 13–14 дивизий в направлении Владимир-Волынский, Луцк, Ровно, Киев против четырех стрелковых и одной танковой дивизии первого эшелона 5-й армии. Наступление поддерживала авиация 4-го воздушного флота, которым командовал генерал Лёр.
Таким образом, противник создал здесь более чем трехкратное численное превосходство, а на направлении главного удара и того больше. Но, несмотря на абсолютное превосходство в силах, ему с трудом удалось преодолеть приграничные укрепления на левом фланге и в центре 5-й армии. К исходу дня он продвинулся на 15–25 км в глубь советской территории.
Обо всем этом, а также о том, что непосредственно перед нами были части 13-й, 14-й танковых и 298-й пехотной дивизий, я узнал после боя, когда на наш КП доставили первых пленных. В минуту же, о которой идет речь, было ясно одно: мы стояли лицом к лицу с противником, и впереди уже горело несколько вражеских танков, подожженных артиллеристами из нашего авангарда. Не медля ни секунды, я приказал главным силам бригады развернуться на рубеже Владимировича – Подгайцы – Микуличи и встретить противника огнем прямой наводки.