В 1928–1931 гг. он – слушатель классов ускоренной подготовки комсостава при ВВМУ им. М. В. Фрунзе, после которых служит в качестве артиллериста, быстро понимаясь по служебной лестнице. В 1933 г. он – командир БЧ-2 эсминца «Володарский». После годичного обучения на курсах усовершенствования Пархоменко назначается помощником командира миноносца «Дальневосточный комсомолец» Амурской флотилии. С 1938 г. он командует миноносцем «Красный восток». В январе 1940 г. в звании капитана 3–го ранга поступает в Военно – морскую академию.
Началась Великая Отечественная война, поэтому 25 июня 1941 г. в Академии был произведен досрочный выпуск недоученных слушателей. Больше Пархоменко учиться не пришлось. Он направляется на Черноморский флот командиром дивизиона канонерских лодок, затем – командиром ряда эсминцев и крейсеров.
В феврале 1948 г. капитан 1–го ранга Пархоменко назначается начальником штаба эскадры Черноморского флота, а через неделю – командующим эскадрой.
В сентябре 1951 г. контр – адмирал Пархоменко сменяет адмирала Горшкова на посту начальника штаба, а 12 июля 1955 г. становится командующим Черноморским флотом.
В то время самым крупным кораблем Черноморского флота был линкор «Новороссийск», бывший итальянский линейный корабль «Джулио Чезаре», переданный Советскому Союзу в качестве трофея в 1949 г.
Корабль имел внушительные размеры и вооружение:
Водоизмещение нормальное, т ………..……………..28 800
Главные размеры, м:
длина по ватерлинии………………………………….182
ширина …………………………………………………..28
осадка …………………………………………….………10,37
Высота надводного борта, м:
в носу ………………………………………….…………7
в корме…………………………………………………… 4
Орудия:
320–миллиметровые, 44 калибра………..…………….10
120–миллиметровые, 50 калибра………..…………….12
100–миллиметровые…………………….……….………8
Толщина брони, мм
борта в средней части …………………………..200–250
в оконечностях ……………………………………..…127
башни главного калибра………………………………280
Мощность главных двигателей, л. с. …………………99 500
Скорость, узлы:
наибольшая……………………………………………..28
экономическая.…………………………………………16