W 1984 roku Frentzen został wicemistrzem w kartingowej klasie 100 cm³. Uczestniczył również w kartingowych mistrzostwach Europy, a jego przeciwnikami byli wówczas m.in. Stefano Modena i Mika Salo. Dwa lata później przeniósł się do Niemieckiej Formuły Ford 2000.
Przed Formułą 1 Heinz-Harald Frentzen zaczął ścigać się w zawodach samochodów jednomiejscowych, gdy miał 18 lat. Przez pierwsze dwa lata jeździł w Niemieckiej Formule Ford 2000 w zespole Eifelland Racing-Albert Hamper. W drugim roku startów w tej serii zdobył tytuł wicemistrzowski.
W 1988 roku Frentzen przeniósł się do Niemieckiej Formuły Opel Lotus. Ścigał się tam w zespole byłego kierowcy Formuły 1 – Jochena Massa, o nazwie Jochen Mass Junior Team. Sezon 1988 był bardzo udany dla całego zespołu – Frentzen zdobył tytuł mistrzowski, a jego kolega z zespołu Marco Werner ukończył mistrzostwa na trzeciej pozycji. Dodatkowo Frentzen przejechał kilka wyścigów w Formule EFDA GM Lotus Euroseries. W ostatnich dwóch wyścigach pokonał Mikę Häkkinena, który następnie został mistrzem tej serii. Frentzen natomiast w klasyfikacji końcowej był szósty z 56 punktami.