Nato a Berlino, Buchholz non conobbe mai il vero padre e prese il cognome dall'uomo, Hugo Buchholz, che la madre, Maria Hasenkamp, sposò nel 1938, di professione calzolaio. Da questa unione nacque la sorella Heidi. Evacuato con la famiglia durante la seconda guerra mondiale prima in Slesia e poi in Cecoslovacchia, al termine del conflitto ritornò a Berlino, dove cominciò molto giovane la sua carriera come attore teatrale, oltre che come doppiatore radiofonico e cinematografico[1][2].
Ottenne il primo ruolo cinematografico di rilievo nel 1954 in Marianne de ma jeunesse di Julien Duvivier, che gli valse un riconoscimento al Festival di Cannes[1], ma la sua affermazione arrivò nel 1956 con la conquista del Deutscher Filmpreis, il più importante premio cinematografico tedesco, quale miglior attore emergente per la sua interpretazione in Cielo senza stelle (1955) di Helmut Käutner[1][3]. Buchholz diventò presto un attore di richiamo commerciale in Germania[1], raggiungendo il grande successo con l'interpretazione de Le confessioni del filibustiere Felix Krull (1957), tratto dal libro di Thomas Mann. Si avviò così a una brillante carriera che lo portò a lavorare con importanti registi sia in Europa che negli Stati Uniti, imponendosi per la sua recitazione energica, la prestanza fisica e il bel volto dai tratti vagamente orientali, lontano dai canoni della bellezza maschile nordica.
Negli anni settanta e ottanta lavorò principalmente per la televisione in vari Paesi. Nel 1976 prese parte a uno dei primi episodi, intitolato Colpo grosso, del celebre telefilm L'ispettore Derrick (I nove casi dell'ispettore Derrick), trasmesso per la prima volta in Italia nel 1979. Interpretò il ruolo di Sergei in alcuni episodi della serie Alla conquista del West, andato in onda in Italia nel 1979, e partecipò alla miniserie italiana Fantaghirò 4 (1994) di Lamberto Bava. Per il cinema, apparve ancora nei film Così lontano così vicino (1993) di Wim Wenders, nel ruolo di un gangster sulla via del pentimento[2], e ne La vita è bella (1997) di Roberto Benigni, nella parte del dottor Lessing, l'ufficiale medico nazista fissato con gli indovinelli, ruolo che gli valse una candidatura agli Screen Actors Guild Awards[2].
Nel 1958 sposò l'attrice francese Myriam Bru, da cui ebbe due figli, Beatrice e Christopher Buchholz; quest'ultimo divenne attore e produsse un documentario sulla vita del padre. La coppia ufficialmente sposata, visse spesso separata: lei a Parigi e lui a Berlino. Si narra anche di una breve relazione precedente con l'attrice Romy Schneider.
Massimo Turci in I magnifici sette, Uno, due, tre!, 9 ore per Rama, Le meravigliose avventure di Marco Polo (Lo scacchiere di Dio), Il grande valzer, Charlie's Angels
