Az 1994-es NHL-draft választotta ki az Ottawa Senators a 133. helyen: játéka a gyengén teljesítő Senatorsba új színt vitt: a csapatból ő játszott egyedül az All-Stars gálán.
Első szerződése lejártával, hosszas egyeztetés után évi 14 millió dollárért újabb négy évre kötelezte el magát a Senatorshoz 1997-ben. A következő szezonban (1998-1999) sérülés következtében csak 11 mérkőzést tudott játszani. A következő szezonban új szerepkörben mutatkozhatott be: Alekszej Jasin távozása után lett az Ottawa Senators kapitánya. A 2003-2004-es szezon után hosszabbították meg a szerződését, ám a kontraktus első évében a kanadai csapatban nem tudta növelni pontjai számát, mivel a lockout közbeszólt. Alfredsson ekkor hazájában, korábbi csapatában, a Västra Frölunda HC csapatában játszott. A 2005-2006-os NHL-szezon során 103 ponttal fejezte be az évadot; ez volt a legeredményesebb idénye - ekkor már Dany Heatley és Jason Spezza voltak a társai az első sorban. Egy évre rá játékával nagyban hozzájárult, hogy a Szenátorok a Stanley-kupáért játszhattak, de azt elbukták. A 2007-2008-as NHL-szezon alapszakaszának a végén a Toronto Maple Leafs ellen sérülést szenvedett, így csapatában a rájátszás első két mérkőzésén nem játszott, a harmadik mérkőzésen tért vissza, nem épülve fel sérüléséből. Teljesítményével azonban nem tudott hozzátenni a Senators játékához: a gárda az első körben kiesett.