Paul was born at Tatoi Palace in Athens, the third son of King Constantine I of Greece and his wife, Princess Sophia of Prussia. He trained as an army officer at the Royal Military College, Sandhurst and later at the Hellenic Military Academy in Kypseli, Athens. Paul was an army officer cadet in the Coldstream Guards and Lieutenant with the Evzones.
From 1917 to 1920, Paul lived in exile with his father, Constantine I. From 1923 to 1935, he lived in exile again in England, this time with his brother, George II. He worked briefly in an aircraft factory under an alias, and through Viscount Tredegar met and befriended notorious literary muse Denham Fouts, who later alleged an affair. However, Fouts's friend John B. L. Goodwin said Fouts often made up stories about his life, and literary critic Katherine Bucknell thought many of the tales about him were myth.