Павел Афанасьевич родился 15 июля 1913 года в городе Енакиево Екатеринославской губернии (Донбасс). В 1927 году семья Гордиенко переехала в Нижний Новгород, где он закончил 7-летнюю школу (1927 г.) и Фабзавуч (1929 г.). Работал токарем, токарем-наладчиком, мастером цеха в паровозном депо станции Нижний Новгород и на Горьковском автозаводе.
В сентябре 1933 года Павел Гордиенко поступил в Московский гидрометеорологический институт на гидрологический факультет. В летне-осенний сезон 1937 года работал гидрологом в системе Главного управления Северного морского пути (ГУСМП) на о. Диксон. В 1938 году закончил обучение в институте, успешно защитив дипломную работу «Ледовые условия плавания по Северному морскому пути в навигацию 1937 года» под руководством выдающегося полярного исследователя, профессора
Н.Н. Зубова. По окончании института Павел Афанасьевич был назначен на работу в систему ГУСМП.
С июня 1938 года по октябрь 1940 года Павел Гордиенко зимовал на полярной станции м. Шмидта в должности старшего гидролога и начальника полярной станции. На основе данных наблюдений, проведенных на мысе Шмидта, Гордиенко написал свои первые научные труды.
По предложению гидролога П.А. Гордиенко и штурмана Московской авиагруппы особого назначения В.П. Падалко состояние ледяного покрова стало оцениваться с использованием единых шкал, а сами авиационные ледовые разведки проводиться по единой методике. [1]