Fjodorov speelde al op 16-jarige leeftijd voor Pachtakor Tasjkent, de enige club uit de Oezbeekse SSR die erin slaagde om ooit in de Sovjet Top Liga te spelen.
Hij speelde achttien wedstrijden voor het nationale elftal en debuteerde op 30 oktober 1974 in een kwalificatiewedstrijd voor het EK 1976 tegen Ierland. In 1976 won hij met de olympische selectie de bronzen medaille op de Spelen in Montreal.