В 1937 году Павел Михайличенко был призван в ряды Красной Армии. Военную службу он начал в г. Новочеркасске солдатом — радистом, а на втором году службы, в 1940 году, он был принят в ряды ВКП (б) и назначен заместителем политрука роты. В 1939-1940 году он окончил курсы младших политруков в г. Ростове-на-Дону и весной 1940 года получил назначение политруком роты в батальон связи. Дивизия, в которую входил батальон, формировалась в городе Ейске. В родном городе Михайличенко находился до мая 1941 года. В мае 1941 года батальон связи в составе дивизии из Ейска перевели в Киевский военный округ, в район города Черкассы. В первые дни Великой Отечественной войны дивизия была переброшена на Западный фронт. Боевое крещение она получила в Смоленском сражении,
которое продолжалось с 10 июля по 10 сентября 1941 года. Дивизия, в которой служил Михайличенко, вела упорные бои с группировкой немецких армий «Центр» в районе городов Рудня, Смоленск, Ельня. После боев под Смоленском остатки ее личного состава влились в стрелковую дивизию, которой 18 сентября 1941 года было присвоено наименование 2-й гвардейской стрелковой дивизии.
Павел Михайличенко стал гвардейцем. Затем Павел Арсентьевич принимал участие в боях в районе городов Рыльск, Льгов, Дмитриев-Льговский, Ростов-на-Дону. 2-я гвардейская стрелковая дивизия, отступая с боями, к началу 1943 года заняла оборону в районе города Нальчик. К этому времени Павел Михайличенко занимал должность заместителя по политической части командира минометного дивизиона. Минометный дивизион 2-ой гвардейской стрелковой дивизии был выделен в отряд, который действовал в районе горы Эльбрус. Павел Арсентьевич осенью 1942 года, по возвращении из горнострелкового отряда, был назначен командиром 3-го гвардейского стрелкового батальона. Вскоре ему было присвоено звание капитан. В январе 1943 года батальон П.А. Михайличенко в дивизии принимал
участие в боях по освобождению городов Нальчик, Минеральные Воды, Железноводск и Кисловодск, Черкесск. А в феврале уже вёл бои по освобождении Кубани: 4 февраля — под станицей Усть-Лабинской (ныне город Усть-Лабинск), а 9 февраля, участвуя в наступлении на Краснодар, обходил его с северо-востока. В бою за станицу Ивановскую батальон под руководством Михайличенко уничтожил до 80 человек солдат противника. За эти бои П.А. Михайличенко был награжден орденом Александра Невского. 26-29 мая 1943 года батальон Михайличенко, к западу от станицы Крымской (ныне города Крымска), у хутора Горищного, удерживал господствующую высоту. За время боев батальон Михайличенко вывел из строя до 300 человек противника, подбил два танка, одно самоходное орудие. За этот бой Павел Михайличенко был награжден орденом Красного Знамени. 7-9 августа батальон под командованием Михайличенко вместе с двумя подразделениями вел ожесточенный бой за хутор Ленинский Крымского района, где они истребили до 180 немецких солдат. Летом 1943 года командиру 3-го батальона Михайличенко было присвоено воинское звание майор. Наступление наших войск на «Голубую линию» на Таманском полуострове началось 10 сентября с боёв за г. Новороссийск. Батальон Михайличенко был посажен на танки и в составе другого соединения принимал участие в освобождении г. Новороссийска, в районе Цемесской долины. Ко времени завершающих боев за освобождение Таманского полуострова, батальон со своим командиром возвратился в родную дивизию. 9 октября 1943 года он воевал на последнем участке кубанской земли — косе Чушка. Во время Керченско — Эльтигенской операции десантную группу по
овладению плацдармом на Крымском полуострове, севернее города Керчи, возглавил П.А. Михайличенко. Ночью 2 ноября 1943 года во время высадки десанта гвардии майор П. А. Михайличенко погиб. Бойцы его батальона похоронили командира в братской могиле на берегу Керченского полуострова. Командование батальоном принял командир первой роты. Подразделения погибшего комбата Михайличенко овладели поселком Маяк (ныне в черте города Керчь) и селом Баксы (ныне Глазовка). Плацдарм у противника был
отвоеван. Задача, поставленная батальону, была выполнена. Гвардейцы 3-го батальона в боях за плацдарм отразили восемь контратак. Они прочно закрепились и расширили плацдарм. На других участках на Крымском полуострове войскам Красной Армии во время Керченско-Эльтигенской десантной операции не удалось закрепиться, после тяжелых боёв все они были оставлены. Бойцы отомстили за гибель своего командира. С плацдарма, захваченного батальоном П.А. Михайличенко, в начале апреля 1944 года Отдельная Приморская армия, освобождая Крым, начала свое наступление. Указом Президиума Верховного Совета СССР от 16 мая 1944 года за мужество и героизм, проявленные в боях за освобождение Крыма, гвардии майору Павлу Арсентьевичу Михайличенко посмертно присвоено звание Героя Советского Союза. В 1975 году на мемориальной доске Обелиска Славы на горе Митридат в г. Керчь были высечены имена 146 Героев Советского Союза и вместе с ними — имя Павла Михайличенко. 11 сентября 2015 года, в рамках акции «Город помнит своих героев» на фасаде здания школы № 5 в городе Ейске, в стенах которой до 1927 года учился П.А. Михайличенко, была открыта мемориальная доска с именем Героя.