En 2000-2001, il commence la saison avec l'équipe de la LAH mais très vite il va faire ses premiers matchs dans la LNH avec les Flyers. Après deux saisons, il prend la direction du Lightning de Tampa Bay avec deux choix de repêchage contre leur premier choix lors du repêchage 2002 (le choix sera Joni Pitkänen). Il gagne avec l'équipe 2003-2004 du Lightning la Coupe Stanley après avoir marqué les deux seuls buts de l'équipe lors d'une victoire 2-1 au septième match de la finale contre les Flames de Calgary[2].
En juillet 2006, le Lightning re-signe Fedotenko pour un contrat d'un an d'un montant de 1,65 million de dollars[3].
Le , il signe un contrat avec les Penguins de Pittsburgh de un an d'une valeur estimée de 2,25 millions de dollars[4]. Lors d'une réunion d'équipe avec le nouvel entraîneur, Dan Bylsma, il suggère à l'équipe un style de jeu offensif, comme celui utilisé lorsqu'il était avec le Lightning de Tampa Bay. Ce style de jeu les avait mené à la Coupe. Lors des séries de 2009, il récolte sept buts, sept passes en 24 matches alors que les Penguins remportent la coupe Stanley. Début , il prolonge d'un an son contrat avec les Penguins[5].
Le il signe un contrat d'une saison de 575 000$ avec le Wild du Minnesota. Il annonce son retrait de la compétition le .