Con la Germania Ovest, Hölzenbein totalizzò 40 presenze e cinque reti dal 1973 al 1978. Il suo momento più importante in Nazionale fu durante la finale del campionato del mondo 1974, quando fece guadagnare alla sua Nazionale il calcio di rigore che portò in parità la partita, poi terminata 2-1 per i tedeschi occidentali. Successivamente però ammise che si buttò a terra nell'area di rigore senza essere toccato dal difensore olandese Wim Jansen.
Nel 1976 egli segnò la rete del 2-2 all'89' nella finale del Campionato Europeo, tuttavia questo non poté impedire alla Cecoslovacchia di vincere il torneo ai rigori.
Dopo il ritiro
Ha lavorato come talent-scout per l'Eintracht Francoforte e in occasione dei mondiali del 2006 è stato insieme a Jürgen Grabowski ambasciatore di Francoforte sul Meno. È scomparso il 15 aprile 2024 all'età di 78 anni dopo una lunga malattia[2].