1999 – 2004: Neuaufbau, Etablierung in der Bundesliga und das „Double“
Nach der Verpflichtung des Trainer/Manager-Duos Schaaf / Allofs 1999 konnte sich Werder nach und nach unter den deutschen Spitzenclubs etablieren. Diese Jahre waren geprägt von der Umstellung auf offensives System, während die Mannschaft gezielt mit spielstarken Spielern verstärkt wurde. Die Mannschaft spielte offensiven und direkten Fussball. Das Potenzial das bereits im SV Werder steckte konnte aber nur phasenweise angedeutet werden, z.B. im Jahr 2000 durch das Erreichen des DFB-Pokalfinals (das leider verloren ging) und indem im Kalenderjahr die meisten Punkte eingefahren wurde.
Der Erfolg wollte sich aber noch nicht kontinuierlich einstellen, 2002 wurde zwar die UEFA-Cup-Qualifikation geschafft, es fehlt aber in deutlichem Mass an der Kontinuität. So folgten auf mehrere herausragende Spiele auch immer wieder Schwächephasen, dies zumeist auch noch gegen Saisonende, wodurch immer wieder sich bietende Chancen nicht genutzt werden konnten. Dieser Umstand trug sicher auch dazu bei, dass junge und vielversprechende Spieler immer wieder abgegeben werden mussten respektive nicht gehalten werden konnten und prominente Neuzugänge selten waren. Werder profitierte aber in dieser Phase durch die Verkäufe von Raphael Wicky im Jahr 2000, Frank Rost 2001 sowie Torsten Frings und Claudio Pizarro 2002. Nachdem Herzog und Wiedener den Verein 2001 verliessen und Marco Bode 2002 altersbedingt aufhörte, fanden sich keine Spieler mehr im Kader aus der „goldenen“ Rehhagel Zeit.
2002/03 konnte sich Werder zwar als Tabellensechster nicht für den UEFA-Cup qualifizieren, konnte aber den französischen Nationalspieler und Spielmacher Johan Micoud, eine echte „Nummer 10“ für sich gewinnen, was wie sich zeigen sollte ein echter Glücksgriff war. Im Ligaspiel gegen Hansa Rostock am 31. März 2002 gelang dem Bremer Keeper Frank Rost mit dem 3:3 kurz vor Spielende als einziger Bundesligatorhüter neben Jens Lehmann ein Tor aus dem Spiel heraus zu erzielen. Am 27. Mai 2003 erfolgte die Ausgliederung der Profifussballmannschaft und der anderen leistungssportlich orientierten Mannschaften in die Werder Bremen GmbH & Co. KGaA.
Die Saison 2003/04 startete blamabel. Das UI-Cup-Halbfinale gegen ASKÖ Pasching (Österreich) wurde mit 0:4 verloren. Wahrscheinlich war dies der ganz grosse Weckruf, denn diese Saison sollte sehr erfolgreich zu Ende gehen. Die talentierte und attraktiv spielende Mannschaft war mit Spielern wie Reinke (ex Kaiserslautern), Davala und Ismaël verstärkt worden. Dies führte einigermassen überraschend dazu, dass sich Werder von Beginn an in der Spitzengruppe der Bundesliga hielt. Am 16. Spieltag wurde die Tabellenführung übernommen und bis zum Schluss nicht mehr abgegeben, der Vorsprung in der Tabelle belief sich bisweilen bis auf 11 Punkte. Werder gewann am 32. Spieltag 3:1 bei Bayern München, dem zweiten der Tabelle und sicherte sich vorzeitig den Titel. Diese Spielzeit war gespickt mit Rekorden: So verlor Werder 23 Spiele in Folge nicht, erst nachdem der Titel gesichert war, ging wieder ein Spiel verloren. Werder wies in dieser Spielzeit zudem die beste Auswärtsbilanz auf, die je ein Bundesligist erzielt hatte.
Zur Krönung holte Werder mit einem 3:2 gegen Alemannia Aachen auch noch den DFB-Pokal und sicherte sich damit erstmalig das Double. Dieses Kunststück gelang in der Bundesligazeit bisher nur dem 1. FC Köln und dem FC Bayern München.