Nacque a Trieste, all'epoca parte dell'Impero Austro-Ungarico, da una famiglia facoltosa. Dopo gli studi all'Accademia Maria Teresa di Vienna e all'Istituto di Arti Grafiche, lavorò come disegnatore e traduttore per una ditta di pubblicità diretta all'epoca da Otto Preminger. Questi lo presentò a Max Reinhardt, che lo invitò a far parte della sua compagnia teatrale a Vienna. Trasferitosi in Inghilterra nel 1935, continuò a recitare in teatro e nel cinema, comparendo - fra gli altri - nel film Addio, Mr. Chips! (1939).
Nel 1940 si stabilì negli U.S.A. e prese la cittadinanza americana. In Perdutamente tua (1942), accanto a Bette Davis, apparve come la quintessenza dell'amatore europeo, colto e sensibile, mentre inCasablanca (1942), di Michael Curtiz, a fianco di Humphrey Bogart e Ingrid Bergman, ebbe la parte di Victor Laszlo, l'idealista che lotta per la libertà. Ambedue questi personaggi esercitarono un grande fascino sul pubblico americano.
Dopo I cospiratori (1944), diretto da Jean Negulesco, Henreid si liberò della sua immagine di esponente di una civiltà esausta, interpretando personaggi di cappa e spada in film come Nel mar dei Caraibi (1945) e Eroi di mille leggende (1952). Nel 1951 esordì come regista con For Men Only; tra i film da lui successivamente diretti è da ricordare Chi giace nella mia bara? (1964) con Bette Davis.
Henreid lavorò anche per la televisione, dirigendo episodi della serie Alfred Hitchcock presenta e Bonanza. Tra gli ultimi ruoli da lui interpretati, generalmente in parti di anziani uomini di potere, è da ricordare il cardinale nel film L'esorcista II - L'eretico (1977).