Frühe Karriere

1919 trat er freiwillig in die Rote Armee ein. Während des Russischen Bürgerkrieges kämpfte er bei den Truppen der Westfront und wurde zweimal verwundet. Von 1923 bis 1924 studierte er an der Wladiwostoker Infanterieschule. Nach der Absolvierung wurde er Zugführer im Infanterie-Regiment 107 von Wladimir. 1929 wurde er Bataillonsführer im 106. Schützen-Regiment der 36. Schützendivision im Militärbezirk Fernost. Für seine dortige Führung erhielt er den Rotbannerorden zuerkannt. Ab Oktober 1930 absolvierte er Kurse für Kommandeure an der Höheren Schützen-Lehreinrichtung „Wystrel“. 1936 wurde er stellvertretender Kommandeur des 106. Schützen-Regiments.

Zu Beginn des Krieges gegen japanische Truppen an der mandschurischen Grenze wurde er auf Vorschlag des Vorgesetzten Kommandeurs Georgi Schukow zum Kommandeur des 24. motorisierten Schützen-Regimentes ernannt und bewährte sich ab Mai 1939 in der Schlacht am Chalchin Gol persönlich als Truppenführer. Am 29. August 1939 wurde Fedjuninski zum Obersten befördert, erhielt den Titel Held der Sowjetunion und wurde mit dem Lenin-Orden und der Goldenen Medaille ausgezeichnet.

Im Deutsch-Sowjetischen Krieg

Zu Beginn des Zweiten Weltkrieges übernahm er im November 1940 das Kommando über die 82. mot. Schützendivision. Am 29. Februar 1940 übernahm er die Führung des 15. Schützenkorps im Raum Kowel. Während der Operation Barbarossa im Bereich der 5. Armee stehend, wurden seine Truppen nach dem Frontdurchbruch der deutschen Panzergruppe 2 im Raum südlich der Festung Brest abgedrängt. Er bewährte sich im Ende Juni während der Rückzugskämpfe in Richtung auf Korosten und wurde für die Übernahme eines neuen Kommandos zur Stawka nach Moskau ausgeflogen. Am 12. August 1941 wurde er zum Generalmajor ernannt. Während der kritischen Phase der Leningrader Blockade wurde Fedjuninski im September 1941 auf Anregung Schukows zu dessen stellvertretenden Kommandeur an der Leningrader Front bestellt. Nach Schukows Versetzung an die Westfront übernahm Fedjuninski im Oktober 1941 vorübergehend das Kommando dieser Front. Er wurde dann Befehlshaber der 42. Armee bei der Verteidigung Leningrads.

Im Herbst 1941 übernahm er am Wolchow die 54. Armee, welche sich in der Schlacht um Tichwin bewährte, aber im Frühjahr 1942 im Rahmen der Ljubaner Operation schwere Verluste erlitt. Ende April 1942 zur Westfront überstellt, kommandierte er im Raum Gschatsk die 5. Armee und wurde am 13. Juni zum Generalleutnant befördert. Im Oktober 1942 wurde er unter General Merezkow stellvertretender Kommandeur der Wolchow-Front. Nach der Operation Iskra (12.–30. Januar 1943) wo er sich im Frontvorsprung von Schlüsselburg und Sinjawino bewährte und schwer verwundet wurde, erhielt er den Kutusoworden 1 Klasse. Im Mai 1943 wurde er zum stellvertretenden Befehlshaber der Brjansker Front ernannt, und am 14. Juli 1943 übernahm er das Kommando über die 11. Armee. Zwischen 1. September und 3. Oktober 1943 befreiten seine Truppen Brjansk und bewährten sich im November an der Offensive zwischen Gomel und Retschyza (10.–30. November 1943).

Am 24. Dezember 1943 wurde er Kommandeur der 2. Stoßarmee im belagerten Raum Leningrad. Während der (Krasnoje Selo-Ropschaer Operation) brachen seine Truppen am 14. Januar 1944 aus dem Brückenkopf von Oranienbaum aus und erreichten eine Woche später die Vereinigung mit der 42. Armee der Leningrader Front. Bis Anfang März wurde dadurch die Leningrader Blockade aufgebrochen. Nach erneutem Stellungskampf gegen den deutschen Brückenkopf von Narva konnte diese Stadt Ende Juli im Zusammenwirken mit der 8. Armee zurückerobert werden. Im Rahmen der Operationen im Raum Tallinn erreichten seine Truppen den Raum um Rakvere, ganz Estland fiel dabei wieder in sowjetischem Besitz. Am 5. Oktober 1944 wurde er zum Generaloberst befördert. Für die Anfang 1945 losbrechende Schlacht um Ostpreußen wurde die 2. Stoßarmee an den Narew-Abschnitt der 2. Weißrussischen Front überstellt. Ab dem 14. Januar 1945 griffen seine Truppen aus dem im Raum Różan an und brachen im Rahmen der Mlawa-Elbinger Operation zur Ostsee durch. Am 10. Februar konnte Elbing eingenommen werden. Nach der Schlacht um Ostpommern wurden seine Truppen zum Angriff auf die letzten deutschen Truppen in Westpreußen umgruppiert, am 30. März fiel Danzig in sowjetische Hand. Für die folgende Operation wurde seine Armee an den nördlichen Oder-Abschnitt bei Stettin verlegt. Ende April nahmen seine Truppen unter Marschall Rokossowski an der Stettin-Rostocker Operation teil, besetzte dabei Stralsund und die dortigen Inseln. Am 24. Juni 1945 nahm Generaloberst Fedjuninski an der großen Siegesparade in Moskau teil. Seine Armee blieb als Teil der Sowjetischen Militäradministration in Deutschland in Mecklenburg (Hauptquartier in Schwerin) stationiert.

Nachkriegszeit

Am 9. Juli 1945 wurde er zum Chef der SMAD für Mecklenburg ernannt, von 1951 bis 1954 fungierte er auch als Stellvertreter des Oberkommandierenden der sowjetischen Besatzungstruppe in Deutschland. 1948 holte er einen höheren akademischen Kurs an der Militärakademie des Generalstabes nach. Von 1948 bis 1951 war er Befehlshaber der 7. kombinierten Armee in Jerewan. Von 1954 bis 1957 war er Befehlshaber des Militärbezirk Transkaukasus, am 8. August 1955 wurde er zum Armeegeneral befördert. Von 1957 bis 1965 war er Befehlshaber im Militärbezirk Turkestan und von 1958 an acht Jahre lang auch Abgeordneter im Präsidium des Obersten Sowjets. 1967 wurde er stellvertretender Oberbefehlshaber der Truppen des Warschauer Paktes. Vom Dezember 1965 bis zu seinem Tod 1977 fungierte er als militärischer Berater im Verteidigungsministerium. In dieser Zeit wohnte er in der Moskauer Gontscharnaja-Straße 26. Er starb 1977 in Moskau und wurde auf dem Nowodewitschi-Friedhof beigesetzt.