Februar 1976 als “Feuerwehrmann” zum SV Werder Bremen, mit einem Vertrag bis Saisonende. Die Norddeutschen stehen am 22. Spieltag auf Platz 14 der Bundesligatabelle und sind vom Abstieg bedroht. Feuerwehrmann Rehhagel soll das machen, was er in den 70-er Jahren häufiger macht: eine Mannschaft kurzfristig zum Erfolg führen und dann wieder gehen.
Die Mission gelingt, die Mannschaft stabilisiert sich und schafft den Klassenerhalt. Nach dem letzten Heimspiel gegen Duisburg (2:0) stürmen die Fans das Spielfeld, tragen Rehhagel auf den Schultern und wollen direkt eine Vertragsverlängerung heraushandeln, die Otto aber dankend ablehnt. Denn er steht schon bei Aufsteiger Borussia Dortmund im Wort.
Im April 1981 kehrt der Erfolgstrainer dann, noch in der 2. Bundesliga, zurück nach Bremen. Und dieses Mal ist er gekommen um zu bleiben. Unter “König Otto” wird Bremen zweimaliger Deutscher Meister (1988, 1993), gewinnt den DFB-Pokal (1991, 1994), den Supercup (1988, 1993, 1994) sowie den Europapokal der Pokalsieger (1992).
Rehhagel prägt den Verein mit seinem absoluten Machtanspruch (“Jeder hat das Recht, meine Meinung zu sagen”) und mit seiner Philosophie der “kontrollierten Offensive”), die attraktiv und von Erfolg gekrönt ist. In seiner Zeit bei Werder wird er vom „Kicker“ viermal zum Trainer des Jahres gewählt.