Так началась моя военная служба, не прерывающаяся с тех пор ни на один день вот уже более полувека…»
После боёв с махновцами отряд Куличенко влился в Первую Конную армию под командованием Семёна Михайловича Будённого, и в её составе потом громил врангелевские войска в Таврии – под Мелитополем, Большим Токмаком и в Крыму. Не случайно в том же году появился знаменитый «Марш Будённого», который написали поэт Анатолий Д’Актиль и музыканты братья Даниил и Дмитрий Покрасс, увековечившие своей песней историю Конармии и её командармов:
Будучи уже маршалом Советского Союза, Кирилл Семёнович Москаленко писал, что служба в Конармии закалила его, молодого тогда комсомольца, воспитала волю, смелость, настойчивость, мужество, привила любовь к Советской Родине и к своему любимому роду войск – кавалерии.
В декабре 1920 года его и нескольких других молодых бойцов направили на курсы комсостава в город Луганск. Но там они учились недолго. Вскоре весь личный состав курсов был брошен на ликвидацию банд Каменюка и «Маруси», бесчинствовавших в то время в донских и луганских степях. После их разгрома, состоявшемся в феврале 1921 года, Москаленко направили в 5-ю Харьковскую артиллерийскую школу, которая была одним из лучших средних военно-учебных заведений того времени. Она имела отборный профессорско-преподавательский состав, входившие в который военные специалисты обладали широкими познаниями и опытом. Во время учёбы в ней курсанты неоднократно привлекались к борьбе с бандами на Харьковщине и Полтавщине.
В сентябре этого года Москаленко вместе с воинской частью был переведён в город Брянск. В то время воины гарнизона шефствовали над брянским заводом «Красный Профинтерн» (ныне производственное объединение БМЗ), и Кирилл Семёнович в этот период неоднократно посещал завод. В знак признательности его деятельности Кириллу Семёновичу было присвоено звание почётного кузнеца завода.
После участия в боях против войск генерала Врангеля на юге Украины и в Крыму, Кирилл Семёнович сражался с различными вооружёнными формированиями на Дону и Северном Кавказе.
В 1922 году, сдав с отличием все экзамены, он был направлен вновь в 1-ю Конную армию, но уже не рядовым бойцом, а командиром взвода конно-артиллерийского дивизиона 6-й Чонгарской кавалерийской дивизии. К тому времени гражданская война закончилась, и лишь на Дальнем Востоке, в Средней Азии и кое-где на Северном Кавказе ещё продолжалась ликвидация контрреволюционных банд. В этих боях довелось поучаствовать и Москаленко, так как 1-я Конная армия в составе 4-й Ленинградской, 6-й Чонгарской, 5-й Блиновской и 14-й Майкопской дивизий находилась на Северном Кавказе. Последней такой операцией на Северном Кавказе для него была ликвидация банд князя Джентемирова.
С начала 1923 года его перевели в Армавир, поближе к штабу дивизии. Зимой дивизион размещался в городе, в хороших казармах, расположенных у впадения прозрачной реки Уруп в мутную, бурную Кубань. Летом вместе со всей артиллерией 1-й Конной армии он выезжал в Персияновские лагеря близ города Новочеркасска. Все дни там были заполнены конной и артиллерийской, а также тактической и строевой подготовкой, да ещё политическими занятиями.
Политсостав, коммунисты были тогда в Красной Армии той мощной цементирующей силой, которая сплачивала весь личный состав в единый организм, в армию нового, революционного типа. Осознавая это, в 1923 году Кирилл Семёнович Москаленко в станице Урупской был принят в кандидаты партии большевиков.
С августа того же года по сентябрь 1924-го Кирилл Семёнович временно исполнял обязанности помощника командира батареи. С мая 1925 года он был уже командиром батареи, а с 1926 года служил в Белорусском военном округе, где командовал артиллерийским взводом, а потом был временно исполняющим должность командира учебной батареи.