Der letzte rettende Halm, musste ein Wechsel sein. Frentzen wechselte zu Jordan Mugen Honda und erlebte seine erfolgreichste Saison. Als Teamkollegen hatte er jenen ehemaligen Weltmeister, dessen Williams-Cockpit er 1997 übernahm: Damon Hill. Frentzen dominierte den lustlos wirkenden Hill, fuhr extrem konstant und schlug 2-mal erfolgreich zu: Beim Frankreich GP gewann er ein schwieriges Regenrennen und beim Italien GP siegte er neuerlich – zum letzten Mal. Aber auch so fuhr er oft aufs Podium, wurde verdient WM-3. und hatte lange Außenseiterchancen auf den Titel. Auch seine Pole beim Europa GP sollte noch Erwähnung finden. 2000 ging es dann aber bergauf, vor allem mit dem Jordan Team, aber auch mit Frentzen. Mit Jarno Trulli bekam Frentzen einen wesentlich stärkeren Teamkollegen und so fuhr Frentzen nur 2-mal aufs Podest: Beim Brasilien- und USA GP wurde er jeweils 3. Der Tiefpunkt war der Italien Grand Prix: Frentzen löste durch eine Kollision mit Trulli einen Massencrash am Start aus, bei dem der 33-Jährige Streckeposten Paolo Ghislimberti sein Leben verlor, weil er von einem umherfliegenden Reifen tödlich getroffen wurde.
2001 schlitterte Frentzen ins Anfang vom Ende. Ab der Saison 2001 ging er am Tiefpunkt seiner Karriere angekommen, doch das Ansehen dadurch wurde nur verstärkt. Die Saison mit dem Jordan Honda verlief von Anfang an schwach, ein 4. Platz beim Malaysia GP tröstet da wenig weg. Es folgten 2 schwere Unfälle, einer beim Monaco GP und einer beim Training zum Kanada Grand Prix. Der 2. Crash war dabei so stark, dass er im Rennen von Ricardo Zonta ausgewechselt wurde. Doch Zonta ersetzte Frentzen nicht nur in Kanada: Am 25. Juli, 4 Tage vor dem Deutschland GP, dem Heimrennen von Frentzen, um kurz nach 13 Uhr kam die Nachricht: Eddie Jordan entlässt Frentzen aus dem Jordan-Vertrag von 2001 und 2002! Frentzen leitete ein Verfahren gegen Jordan ein. Der Rausschmiss kam unerwartet, denn erst beim Europa GP wenige Monate zuvor verlängert Jordan den Vertrag mit Frentzen bis Ende 2002. Die Leistungen von Frentzen allerdings waren nicht unbedingt stark 2001, was freilich auch an Pech lag und seinen Unfällen, aber auch, weil Teamkollege Trulli in der Gesamtheit die deutlich bessere Figur machte: Im Quali war Frentzen im Schnitt 0,3 Sekunden langsamer als Trulli, im Startduell stand es 1:9 für den Deutschen und in WM Punkten gemessen lag Frentzen mit 6:7 zurück. Frentzen fühlte sich im Jordan-Team gegenüber Trulli benachteiligt und gab dies auch lautstark der Presse bekannt.
Frentzen war nach dem Rausschmiss bei Jordan auf intensiver Jobsuche. Mit 34 Jahren gehörte er schon zum älteren Eisen, doch er besaß eine Menge Erfahrung, Technikverständnis und auch die wenigsten konnten glauben, dass sein Talent auf der Strecke geblieben war. Der perfekte Fahrer für das 2002er Neueinsteigerteam Toyota, die neben Mika Salo noch auf der Suche nach einem 2. Fahrer waren, doch Frentzen gaben sie sehr schnell eine Absage. Es sah nicht gut aus um Frentzen, er selbst sah kaum noch Chancen in der F1 zu verbleiben, doch die Pause dauerte nur ein Rennen: Beim Ungarn GP kehrte Frentzen wieder zurück; Prost Acer verpflichtete ihn an Stelle von Jean Alesi, der im Gegenzug bei Jordan Honda den Frentzen-Ersatz Zonta ersetzte. Frentzen landete mit dem Prost-Team bei einem finanziell schlecht sortierten Team, das auch keine Topadresse in Sachen Leistung war. Doch Frentzen zeigte wieder Motivation – das fehlte ihm Anfang 2001. Beim Belgien GP stellte Frentzen den blauen Prost sensationell auf Startplatz 4! Das Rennen beendete er nach vielen Problemen aber nur auf Rang 9. Das Prost Team ging Ende 2001 Pleite, Frentzen wechselte zu Arrows Ford und fand sich neuerlich in einem Hinterbänklerteam wieder.
Frentzen schöpfte mit seinem Talent das Potenzial des Arrows Renners immer wieder aus. 2-mal, nämlich beim Spanien- und Monaco GP fuhr er mit Rang 6 jeweils verdient in die Punkte. Doch danach ging es bergab. Das Arrows Team hatte finanzielle Schwierigkeiten, insbesondere gab es Streitereien mit Teilhabern und so wurde die Luft auch für Frentzen ab Mitte der Saison dünn. Frentzen musste das Arrows-Spiel mitspielen und das hieß beim Frankreich GP, dass er so langsam fahren musste, dass er sich nicht qualifizieren konnte, weil das Team kein Geld für den Start hatte. Beim folgenden Grand Prix in Deutschland war Arrows nochmals am Start, doch danach war Schluss für das Team und damit vorzeitig auch wieder für Frentzen. Der Vertrag mit Arrows ging auch ins Jahr 2003. Gemeinsam mit Sébastien Bourdais sollte Frentzen die Arrows-Fahrerpaarung für 2003 stellen. Doch wegen seinen überzeugenden Auftritten bei Prost und Arrows war Frentzen für 2003 wieder hoch im Kurs. Mehrere Teams zeigten Interesse, Sauber, Jaguar, Toyota, Minardi und sogar Jordan wollte ihn zurück haben! Frentzen machte auch eine Teamrückkehr, aber nicht zu Jordan, sondern zu Sauber, also zu jenem Team, bei dem alles in der Formel-1 begann. Peter Sauber wollte Frentzen bereits für die Saison 2001 zurückholen, doch damals entschied sich Frentzen für Jordan, wie er selbst bemerkt hat, war dies eine glatte Fehlentscheidung. Beim USA GP 2002 durfte Frentzen sogar schon erstmals im Sauber Platz nehmen, weil er für ein Rennen Felipe Massa vertrat.
2003 fuhr er dann eine ganze Saison für Sauber Petronas, neben seinem Landsmann Nick Heidfeld. Heidfeld kommt nicht nur aus dem gleichen Land Deutschland, sondern sogar aus der gleichen Stadt Mönchengladbach. Heidfeld und Frentzen bildeten das erste und bislang einzige Städtepaar in einem Team in der Formel-1. Die bessere Figur im Rennauto machte Frentzen. Die Saison allerdings wurde schwierig, denn Sauber litt unter die mangelhafte Konkurrenzfähigkeit der Bridgestone Pneus und war kaum ein Punkteanwärter. Nur beim USA GP, dem vorletzten Rennen in der F1-Karriere von Frentzen, fuhr er mit Rang 3 noch einmal aufs Podium und absolvierte sogar Führungsrunden! Frentzen setzte noch einmal ein Highlight, trat dann jedoch nach 157 WM Rennen, 3 Siegen, 2 Poles und 174 WM Punkten aus der GP Szene ab. Ein Angebot von Jordan für die Saison 2004 schlug Frentzen aus.
Der Wechsel in die Deutsche Tourenwagenmeisterschaft DTM war perfekt, für 2004 wechselte Frentzen ins Holzer DTM Team. Die Saison lief nicht nach Wunsch, Frentzen wurde nur Gesamt-14. und war damit der schlechteste Holzer-Opel Fahrer. Auch Timo Scheider und Manuel Reuter, beide ohne Formel-1 Erfahrung fuhren noch Opel Renner für das Holzer Team. 2005 fuhr er weiter einen Opel in der DTM, dieses Mal erfolgreicher. Er war bester Fahrer des OPC Teams und fuhr sogar 2 Podiums ein. Ebenfalls für das OPC Team fuhren Laurent Aiello (der Franzose testete 1994 und 1995 für Jordan einen Formel-1-Boliden und wurde für Abt-Audi 2002 DTM Meister), Marcel Fässler (der Schweizer testete 2001 für McLaren Mercedes) und Reuter. Frentzen fuhr 2006 noch eine DTM Saison für das Audi Team Abt, fuhr wieder 2-mal aufs Podium und beendete die Saison als 7. Tom Kristensen, Martin Tomczyk und Mathias Ekström (der Schwede wurde 2004 DTM Champion) waren Frentzens Teamkollegen, die ersten beiden platzierten sich in der Gesamtwertung vor Frentzen. 2007 macht Frentzen mindestens eine Pause vom Rennsport, ein Rücktritt könnte zur Jahresmitte erfolgen.
Jochen Mass, der Sieger des Spanien GP 1975, war jener Fahrer bei Mercedes Benz, der die 3 Junioren Frentzen, Wendlinger und Schumacher 1990 für höhere Aufgaben qualifizieren sollte. Mass erinnert sich: „Alle 3 waren sehr schnelle Jungs, aber jeder hatte andere Stärken und Schwächen. Was mich bei Heinz-Harald überraschte, war seine Fähigkeit, auf Anhieb schnell zu sein. Bei einem Testtag in Jerez hatte er noch keine fliegende Runde gedreht, aber dafür machte er Witze mit den Mechanikern, bis ich rüberging und ihm sagte, er solle sich besser aufs Fahren konzentrieren. Da war er zwar etwas eingeschnappt, doch er fuhr raus und drehte seine erste fliegende Runde - die auch prompt die schnellste des Tages war.“