Après l’obtention de son diplôme en 1927 dans un internat privé de Vienne, il étudie à l'Institut des arts graphiques avec l'intention de devenir un éditeur de livres. Il a travaillé pendant quatre ans comme concepteur de livres et traducteur tout en fréquentant la nuit la prestigieuse Académie Maria Theresa de Vienne, où il a commencé à s'intéresser au septième art malgré les objections de sa famille. Lors d'une performance dans une école de théâtre, il a été découvert par Otto Preminger, le directeur général de Max Reinhardt, et débute sur scène sous sa direction.

Dès 1932 il apparaît dans deux films autrichiens sous le nom de Paul von Hernreid avant de s'installer en Angleterre en 1937 en raison de la montée du nazisme. A Londres, il remporte un certain succès en jouant le Prince Albert dans la production théâtrale « Victoria Regina ». Paradoxalement à ses sentiments anti nazi il débute au cinéma en 1939 jouant un jeune professeur d'allemand dans «Au revoir, M. Chips » de Sam Wood avec Greer Carson ; un officier nazi dans « Amour d’espion » d’Albert de Courville avec Edmund Gwenn et un agent de la gestapo dans « Train de nuit pour Munich » (1940) de Carol Reed avec Margaret Lockwood.

En 1940, il s'installe définitivement aux États-Unis et devient citoyen américain en 1941, très vite il se fait remarquer à Broadway en interprétant un docteur nazi dans la pièce de théâtre « Flight to the West » (1940). Un succès qui l'a aidé à obtenir un contrat à Hollywood, avec la RKO Radio Pictures. Dans son premier film hollywoodien « Jeanne de Paris » (1941) Robert Stevenson le libère de son stéréotype germanique et lui offre le rôle d’un pilote français dont son avion à été abattu, il trouve refuge chez Jeanne (Michèle Morgan) une jeune serveuse du café, ils tomberont amoureux. En 1942, il passe à la Warner Bros et obtient un rôle phare dans le classique « Casablanca » (1942) de Michael Curtiz avec Humphrey Bogart et Ingrid Bergman, il interprète le chef de la résistance tchèque Victor László, échappé d'un camp de concentration. A contre emploi il tient un rôle romantique dans « Une femme cherche son destin » (1942), de Irving Rapper il rencontre et tombe profondément amoureux de Charlotte (Bette Davis) mais il est marié la scène ou il allume deux cigarettes en même temps et, en tend une à Bette Davis est restée dans les mémoires.

Il enchaîne avec un film dramatique teinté de romantisme « Dans notre temps » (1943), de Vincent Sherman , il incarne un comte polonais qui avec sa femme anglaise (Ida Lupino) ils se battent contre les envahisseurs nazis ; puis sur fond de guerre, un résistant dans « Les conspirateurs » (1944) de Jean Negulesco, il tente de démasquer un traite dans un groupe de conspirateurs, il y a Irène (Hedy Lamarr) une ancienne connaissance dont il tombe amoureux, mais serait' elle la traite ?. Il change de registre avec « La vie passionnée des sœurs Brontë » (1945) de Curtis Bernhardt, deux sœurs Charlotte (Olivia de Havilland) et Emily (Ida Lupino) se livrent à des intrigues et à des passions très romantiques auprès d'un prêtre (Paul Henreid). Dans le film noir au suspens haletant « Le balafré » (1948) de Steve Sekely, il joue un double rôle, pour échapper à la justice après un hold-up manqué, il endosse la personnalité d'un docteur, un sosie que seul une balafre au visage peut l'identifier avec Eduard Franz et Joan Bennett.

Dans un drame carcéral « Les dépravés » (1950) de Bernard Vorhaus, le psychiatre John Jason (Paul Henreid) découvre grâce à Loretta (Anne Francis), le traitement sadique que subissent les filles par les matrones dans une école pour jeunes délinquantes. Il se voir endossé le personnage du pirate « Jean Lafitte, dernier des corsaires » (1950) de Lew Landers avec Karin Booth et Mary Anderson; tout aussi à l’aise dans film d'aventure fantastique « La sirène de Bagdad » (1953) de Richard Quine, dans l'empire médiéval perse , il est Kazah le Grand un magicien itinérant , qui cherche à récupérer sa troupe de belles danseuses qui doivent être vendues en esclavage avec Patricia Medina la princesse Zandi. Il retrouve Patricia Medina dans « Les pirates de Tripoli » (1954) de Felix E. Feist dans le rôle de la princesse Karjan qui promet au capitaine pirate Edri-Al-Gardian (Paul Henreid) une fabuleuse récompense s'il l'aide à retrouver son royaume perdu.

Alors que sa carrière est à son apogée, il se retrouve inscrit sur la liste noire en tant que sympathisant communiste par HUAC ce qui a pratiquement achevée sa carrière fin des années 1950. Dès lors, Paul Henreid passe à la production et réalise un thriller haletant « La mort frappe trois fois » (1963), une ouvrière (Bette Davis) assassine sa riche soeur jumelle par vengeance et usurpe son identité pour profiter de sa fortune avec Karl Malden et Peter Lawford. Il réalise aussi une trentaine de séries télévisées faisant de temps à autre un film au grand écran , il tourne son dernier tenant le rôle d'un cardinal dans « L’exorciste II : L’hérétique « (1976) avec Linda Blair, Richard Burton et Max von Sydow.

Paul Henreid épouse Elizabeth Camilla Julia (née Glück) le couple a adopté deux filles, ils sont restés unis jusqu’au décès de l’acteur le 19 mars 1992 d’une pneumonie à Santa Monica, en Californie, après avoir subi un accident vasculaire cérébral. Il repose au cimetière de Woodlawn à New York. Son épouse là rejoint l’année suivante.