V armádním klubu odstartoval svou hvězdnou kariéru, v lize za něj poprvé nastoupil v 16 letech. V roce 1990 odešel do NHL, kde nastupoval dvě desetiletí. S Detroitem vyhrál třikrát Stanley Cup a získal i cenu pro nejužitečnějšího hráče soutěže.
Trojnásobný mistr světa a majitel dvou olympijských medailí oblékal rovněž dres Anaheimu, Columbusu a Washingtonu.
V NHL skončil v roce 2009, pak hrál ještě v Rusku za Magnitogorsk a v roce 2013 se chystal znovu naskočit na led i za CSKA, ale nakonec z toho sešlo.
V klubu začal pracovat jako funkcionář. V roce 2015 byl Fjodorov uveden do hokejové Síně slávy, o rok později vstoupil do Síně slávy Mezinárodní hokejové federace (IIHF).
