Bereits im Januar 1996 hatten die Islanders und die Senators sich geeinigt, Redden gemeinsam mit Torwart Damian Rhodes gegen Berard, Don Beaupre und Martin Straka zu tauschen. Und so startete der Verteidiger zur Saison 1996/97 für die Ottawa Senators seine NHL-Karriere. Redden erfüllte die in ihn gesetzten Hoffnungen und entwickelte sich zu einem der besten Verteidiger der NHL. Mit seinen hervorragenden Fähigkeiten war er auch immer wieder in den Scorerlisten zu finden und in der Saison 2005/06 schaffte er erstmals 50 Punkte. Eine besondere Stärke von Redden war die Spieleröffnung. Auch bei internationalen Turnieren war Redden während der Zeit in Ottawa immer wieder für die kanadische Nationalmannschaft aktiv. Er spielte in den Jahren 1999, 2001 und 2005 bei der Weltmeisterschaft. Darüber hinaus gewann er den World Cup of Hockey 2004 und gehörte zum Kader Kanadas bei den Olympischen Winterspielen 2006 im italienischen Turin.
Nach elf NHL-Spielzeiten mit den Ottawa Senators unterzeichnete Redden im Juli 2008 einen Vertrag bei den New York Rangers, der ihm bei sechs Jahren Vertragslaufzeit 39 Millionen Dollar einbringen sollte. Allerdings konnte der Verteidiger nicht an seine bisherigen Leistungen anknüpfen und geriet immer weiter in die Kritik. Die New York Post bezeichnete den Vertrag 2009 als den „Schlechtesten in der Geschichte der NHL“.[1] Nach zwei Spieljahren wurde der Verteidiger schließlich zu den Connecticut Whale, dem Farmteam der Rangers in der American Hockey League, beordert und in der folgenden Saison zum Kapitän der Mannschaft ernannt. Nach dem Auslaufen des NHL Collective Bargaining Agreement und dem darauf folgenden Lockout entschied das Management der Rangers vor Beginn der Saison 2012/13 allerdings, Redden nicht erneut in den Kader des Farmteams zu berufen, und so sein vorgesehenes Saisongehalt von fünf Millionen Dollar nicht zahlen zu müssen.[2]
Nach Ende des Lockouts wurde Redden schließlich am 18. Januar 2013 aus seinem Vertrag freigekauft.[3] Noch am selben Tag unterzeichnete er als Free Agent einen neuen Einjahresvertrag mit den St. Louis Blues.[4] Am 3. April 2013 wurde er zu den Boston Bruins transferiert. Nachdem er zu Beginn der folgenden Spielzeit ohne Verein geblieben war, gab Redden im Januar 2014 das Ende seiner aktiven Laufbahn bekannt.[5] Nach mehr als zweijähriger Pause wurde Redden im Sommer 2016 für den Posten des Assistant Director of Player Development bei den Nashville Predators aus der NHL verpflichtet.
(Legende zur Spielerstatistik: Sp oder GP= absolvierte Spiele; T oder G= erzielte Tore; V oder A= erzielte Assists; Pkt oder Pts= erzielte Scorerpunkte; SM oder PIM= erhaltene Strafminuten; +/−= Plus/Minus-Bilanz; PP= erzielte Überzahltore; SH= erzielte Unterzahltore; GW= erzielte Siegtore; 1Play-downs/Relegation; Kursiv: Statistik nicht vollständig)