1927年ウクライナのフメリニツキーに生まれる。父親は軍人であったが、スターリンの大粛清の犠牲となった。パイロットを目指してロストフの航空学校に入るが、市街電車に飛び乗ろうとして電車に轢かれ左足を失い、パイロットへの道は閉ざされてしまった。しかし、フョードロフは不屈の闘志を発揮し、自分で義足を改良し、水泳で全国チャンピオンになるという快挙を成し遂げる。その後、眼科医を目指すようになり、1952年にロストフ医科大学を卒業する。
アルハンゲリスク医科大学眼科医長、ロシア共和国保健省実験・臨床外科学研究所所長などを歴任する。1974年に角膜に傷を入れる独自の近視治療手術を考案し、注目されるようになる。ゴルバチョフによって、ペレストロイカが開始されると近視矯正手術をビジネスとしてフョードロフ病院(正式名称、眼科ミクロヒルルギア研究所)を設立する。病院からホテル、農場、カジノ経営まで手広く事業を行った。出身は国営大企業からでもなく、ユダヤ系でもなく、異色のオリガルヒである[1]。
政治家としても、ゴルバチョフの顧問となったのを手始めとして、民主改革派としてアレクサンドル・ヤコブレフらと行動を共にし、1989年から1991年までソ連人民代議員大会と最高会議の代議員を務め、この間地域間代議員グループに所属した。
ソ連崩壊後は、1995年に下院国家会議代議員に当選。1996年6月、ロシア大統領選挙に立候補し、69万9000票を獲得するが6位で落選する。1999年に政治ブロック「フョードロフ・ニコラエフ連合」を結成して下院選挙に臨んだが、落選した。
70歳を超えても、その活動は精力的で、片手で30kgの鉄アレイを持ち上げたり、ヘリコプターの操縦訓練を受けていた。2000年6月ヘリコプター墜落事故で死去。