Ruslan Fedotenko empezó jugando al hockey hielo en su ciudad natal en Kiev (Ucrania) y, desde muy joven, con 16 años, en la temporada 95-96 comenzó a disputar los primeros partidos en el primer equipo del Sokol Kiev. Pasados dos años, cruzó el charco para jugar en una liga Junior en Canadá, en la SJHL con Melfort Mustangs y, la temporada siguiente la disputó en la USHL (la liga Junior de más alto nivel de EEUU) en las filas de los Sioux City Musketeers, donde anotó la friolera cantidad de 43 goles en 55 partidos.

Posteriormente, dio el paso a la NHL firmando con los Philadelphia Flyers en 1999. En su primera temporada con los Flyers, 2000-2001, no pasó desapercibido y sumó 16 goles más 20 asistencias en 74 partidos. En el verano de 2002, fue traspasado a Tampa Bay Lightning.

En la franquicia del estado de Florida fue donde cosechó sus mayores éxitos como jugador de NHL. En primer lugar, consiguió con Tampa en la temporada 2003-2004 la Stanley Cup, siendo determinante en los Playoffs anotando 12 goles y, además, marcó el segundo gol para su equipo en el séptimo partido ante los Calgary Flames en la victoria por 2-1. A nivel personal en la NHL, fue la temporada 2005-2006 la mejor para él: con 26 goles y 15 asistencias.

Fedotenko sería trasladado en la temporada 2007-2008 a los New York Islanders, donde solo estaría ese año y donde tuvo una discreta actuación. Al finalizar la campaña vuelve a cambiar de equipo, esta vez para recalar en las filas de los Pittsburgh Penguins. En su segunda temporada en Pensilvania consiguió su segunda Stanley Cup, teniendo una gran actuación, nuevamente, en la post-temporada.

En 2010, volvió a Nueva York, pero esta vez para recalar en los Rangers y, tras dos temporadas, retornó a su primer equipo de la NHL, los Flyers para concluir su carrera en la mejor liga del mundo. Sus dos últimos años como jugador de hockey, en la temporada 2014-15 y 2015-16 los ha pasado en la AHL en los Iowa Wild.

Ruslan Fedotenko pone fin a una larga carrera, donde ha disputado 863 partidos en la NHL, en los cuales ha anotado 173 goles y repartido 193 asistencias. A sus marcas individuales se suman las dos Stanley Cups ganadas con Tampa y los Penguins.