Né Henry Bookholt, fils de cordonnier, Horst Buchholz débute sa carrière à la radio et sur les planches, avant de travailler pour un studio de doublage. Découvert dans un théâtre berlinois dans les années cinquante par le cinéaste français Julien Duvivier, il fait ses débuts sur grand écran sous sa direction en 1954, avec un petit rôle dans Marianne de ma jeunesse, avant de reprendre le rôle principal du film, tenu par Pierre Vaneck, dans une version allemande l'année suivante, toujours mise en scène par Duvivier. La même année, il obtient le prix du Meilleur acteur au Festival de Cannes pour son rôle dans Sky without stars de Helmut Kautner.

Confirmant son succès international avec des films comme Les Confessions de Felix Krull en 1957, Horst Buchholz décide de tenter sa chance à Hollywood, et abandonne ses rôles romantiques pour des personnages plus durs. Sa carrière américaine débute avec Les Yeux du témoin de Jack Lee Thompson en 1959. En 1960, il incarne l'un des Sept mercenaires de John Sturges, aux côtés de Yul Brynner et Steve McQueen, puis joue sous la direction de Billy Wilder dans la comédie Un, deux, trois. Variant les genres, il s'essaiera au film historique (La Fabuleuse aventure de Marco Polo, 1963), au drame romantique (Fanny, version américaine de la trilogie de Marcel Pagnol, 1961), le thriller (Touch and Die, 1991), le drame (Si loin, si proche, 1992), l'action (L'Aigle de fer III, 1991) ou le dessin animé (Mulan, 1998). Se cantonnant à des productions télévisées ou des films sans grande envergure sur la fin de sa carrière, il incarne l'officier nazi pativé par les énigmes de Roberto Benigni dans La vie est belle.

Marié à l'actrice française Myriam Bru en 1958, Horst Buchholz est le père du comédien Christopher Buchholz.