Als Spieler

Fedotow begann seine Karriere bei Uralmasch Jekaterinburg. In der Saison 1983 absolvierte er zwei Partien für die erste Mannschaft Uralmaschs in der dritten sowjetischen Liga. Zur Saison 1983 wechselte er zum ebenfalls drittklassigen Druschba Joschkar-Ola. Für Druschba kam er in zwei Spielzeiten zu 53 Einsätzen. Zur Saison 1986 kehrte er nach Jekaterinburg zurück. Dort kam er zu 26 Einsätzen. Wo er in der Saison 1987 spielte, ist nicht bekannt. In der Saison 1988 war er für den Viertligisten Metallurg Werchnjaja Pyschma aktiv, zu jenem Zeitpunkt Farmteam von Uralmasch. Zur Saison 1989 wechselte er schließlich ein drittes Mal zu Uralmasch. Mit Uralmasch stieg er 1990 in die zweite Liga auf. Nach der Auflösung der Sowjetunion wurde Uralmasch 1992 in die erstklassige russische Premjer-Liga eingeteilt. Daraufhin debütierte Fedotow im März 1992 gegen den FK Fakel Woronesch in der höchsten Spielklasse. Insgesamt kam er zu 141 Einsätzen für Uralmasch in der Premjer-Liga.

Nach acht Jahren in Jekaterinburg wechselte der Abwehrspieler zur Saison 1997 zum Drittligisten Arsenal Tula. Mit Tula stieg er zu Saisonende in die zweite Liga auf. Zur Saison 1999 wechselte er innerhalb der zweiten Liga zu SOJUS-Gasprom Ischewsk. Dort kam er zu 40 Einsätzen in der Perwenstwo FNL. Zur Saison 2000 schloss er sich dem Ligakonkurrenten PFK Sokol Saratow an. Mit Sokol stieg er zu Saisonende in die Premjer-Liga auf. Nach insgesamt 63 Erst- und Zweitligaeinsätzen für den Klub kehrte er im Juli 2002 noch einmal nach Jekaterinburg zurück, wo der inzwischen nur noch Ural genannte Verein mittlerweile wieder nur noch drittklassig war. Mit Ural stieg er am Ende der Spielzeit 2002 noch einmal in die zweite Liga auf. Nach dem direkten Wiederabstieg beendete er nach der Saison 2003 schließlich seine Karriere. Fedotow war lange Zeit der Rekordspieler Urals in der Premjer-Liga, ehe er in der Saison 2019/20 von Denys Kulakow abgelöst wurde.

Als Trainer

Fedotow wurde nach seinem Karriereende Co-Trainer bei Ural Jekaterinburg. Im Juli 2009 übernahm er den Zweitligisten als Chefcoach. Unter seiner Führung belegte das Team in der Saison 2009 den achten Rang in der zweiten Liga. Nach einem misslungenen Saisonstart 2010 mit drei Siegen aus den ersten neun Spielen und insgesamt vier 0:0-Remis trennte sich der Klub im Mai 2010 von Fedotow. Zur Saison 2011/12 wurde er Trainer des Drittligisten Metallurg-Kusbass Nowokusnezk. Nowokusznezk führte er direkt in seiner ersten Spielzeit beim Verein zum Zweitligaaufstieg. Nach der Saison 2012/13 zog sich der Verein allerdings aufgrund finanzieller Probleme aus der zweiten Liga zurück. Daraufhin verließ Fedotow den Klub.

Zur Saison 2015/16 wurde er Co-Trainer von Robert Jewdokimow beim Zweitligisten Gasowik Orenburg. Mit Gasowik stieg er zu Saisonende prompt in die Premjer-Liga auf. Der inzwischen in FK Orenburg umbenannte Klub stieg allerdings nach einer Spielzeit prompt wieder in die Perwenstwo FNL ab, woraufhin Jewdokimow den Klub verließ. Fedotow folgte ihm als Cheftrainer nach und führte den Verein 2017/18 zum Zweitliga-Meistertitel und dem damit verbundenen direkten Wiederaufstieg. In der Saison 2018/19 gelang mit Rang sieben zudem auch souverän der Klassenerhalt in der Premjer-Liga. Im Dezember 2019 wechselte er zum Ligakonkurrenten FK Sotschi. Sotschi, das er als Tabellenletzter übernommen hatte, führte er mit Rang zwölf zum Klassenerhalt. War der Verein 2019/20 noch im harten Abstiegskampf, so war man in der Saison 2020/21 immer in der oberen Tabellenhälfte vertreten. Zu Saisonende stand schließlich der fünfte Rang zu Buche, womit Fedotow Sotschi zum ersten Mal in der Vereinsgeschichte in den Europacup geführt hatte. In der Qualifikation zur UEFA Europa Conference League in der Folgesaison war allerdings in der dritten Runde gegen den FK Partizan Belgrad Endstation. In der Saison 2021/22 wurde er mit Sotschi erstmals in der Vereinsgeschichte Vizemeister.

Zur Saison 2022/23 wechselte Fedotow innerhalb der Liga zu ZSKA Moskau.