Paolo nacque, nel 1901, ad Atene, terzo figlio di Costantino I e di sua moglie, la principessa Sofia di Prussia. Seguì la carriera militare in marina, divenendo ufficiale.
Dal 1917 al 1920 Paolo visse in esilio con il padre Costantino I. Dal 1923 al 1935, e ancora dal 1941 al 1946, visse nuovamente in esilio, questa volta con il fratello Giorgio. Durante gran parte della Seconda guerra mondiale, quando la Grecia era sotto l'occupazione nazista, egli si trovava in esilio con il governo greco a Londra, dove, come suo fratello Giorgio, fu iniziato in massoneria, ed al Cairo. Dal Cairo inviava lettere e libelli al popolo greco.
Nel 1949 la guerra civile terminò ufficialmente con la vittoria degli anticomunisti.
Negli anni '50 la Grecia ritrovò una certa stabilità economica e le relazioni diplomatiche all'estero erano sostenute dalle continue visite ufficiali compiute da Paolo presso altri Stati. Egli fu il primo monarca di Grecia a far visita ad un capo di Stato turco. I legami con la Gran Bretagna si incrinarono per la questione di Cipro, dove la maggior parte degli abitanti era intenzionata ad entrare a far parte della Grecia (Enōsis), cosa che metteva a rischio i diritti della minoritaria comunità turco-cipriota e la stessa volontà del Regno Unito, che preferiva la nascita di una nuova entità statale per mantenere alcune sue importanti basi militari.
Nel dicembre 1959 il principe Massimiliano di Baviera consegnò alla Grecia i tesori della corona del re Ottone I di Grecia, esportati dalla Grecia quasi cent'anni prima.
Ne frattempo in Grecia cresceva sempre più forte il sentimento repubblicano. Il re stesso si attirò numerose critiche per i suoi continui viaggi e per i costi del mantenimento della famiglia reale. Egli rispose alle proteste con un maggior autocontrollo economico e la donazione della sua residenza privata di Polidendri allo Stato.