Павел Васильевич Панченко-Криворотенко получил образование в Ейском реальном училище. На службу поступил 15 августа 1892 года; окончил Казанское пехотное юнкерское училище (1898). Из училища выпущен подпоручиком (ст. 26.01.1898) в 7-й гренадерский Самогитский полк. Получил звание поручика (ст. 26.01.1902), штабс-капитана. Окончил Николаевскую академию Генерального штаба (в 1907 г. — по 1-му разряду). Получает звание капитана (ст. 07.05.1907). 

Цензовое командование ротой Панченко-Криворотенко отбывал в 7-м гренадерском Самогитском полку (06.11.1907-11.11.1909). Был обер-офицером для поручений при штабе Казанского ВО (26.11.1909-02.10.1910), помощником старшего адъютанта штаба Казанского ВО (02.10.1910-17.01.1911), старшим адъютантом штаба 41-й пехотной дивизии (17.01.1911-09.08.1912), старшим адъютантом штаба 10-го армейского корпуса (с 09.08.1912). 

П.В. Панченко-Криворотенко участвовал в Первой мировой войне, во время которой получил звание подполковника (пр. 06.12.1914 — ст. 06.12.1913) с назначением штаб-офицером для поручений при штабе того же корпуса, затем —звание полковника (ст. 06.12.1915); позднее он был назначен исполняющим должность начальника штаба 31-й пехотной дивизии (с 14.06.1915 — на 03.01.1917 в должности) ; награжден Георгиевским оружием (ВП 13.10.1916). 

В 1917 году он получает звание генерал-майора, назначается начальником штаба 129-й пехотной дивизии (с 25.11.1917); служил в армии Украинской Державы (с 21.04.1918). 19 июля 1918 г. он был назначен начальником штаба 4-го Киевского корпуса. 12 октября 1918 г. П.В. Панченко-Криворотенко был назначен начальником штаба 7-го Харьковского корпуса. С 19 декабря 1918 г. он возглавлял добровольческий отряд в Харькове, который входил в состав сил Директории УНР, но позже перешел на сторону ВСЮР. С 08 января 1919 г. он находился в резерве чинов при штабе Главнокомандующего ВСЮР.