Having left Russia for Belgium in 1908, with a further move to France, Fyodorov was still living in the latter when World War I began.
After several candidates had been found wanting, Fyodorov was sent "...a kid from the Class of '16....Dirty, not groomed, unshaven, swimming in those large blue pants, drenched in oil...." After flying a Caudron tuned by young Caporal Pierre Lanero, Fyodorov landed to proclaim, "Now I am able to be at ease, my back does not hurt and does not vibrate.
In the ensuing gun battle, Lanero shot down a German plane, and the Caudron suffered 17 bullet holes.
They were shot down in combat with three German planes, with a wounded Fyodorov barely able to pull off a crashlanding through some wire fences in a mountain meadow.
[4] A promotion into the officer's ranks, as a Sous lieutenant, came on 9 August 1916, with a personal thanks for his service rendered by General Joffre.
A strain of homesickness inhabited his correspondence at that time as he applied to join the French Military Mission to Romania.
When the six pilots of the understrength squadron relocated to Tecuci, Fyodorov was close enough to Russia to apply for instatement into the Imperial Russian Air Service.
Fyodorov objected to rear echelon duties, and was returned to combat,[2] posted to the 11th Korpusnoi Aviatsionniy Otryad (Corps Aviation Detachment) commanded by Alexander Kazakov.
Lanero became well known for his mechanical skills while maintaining Fyodorov's Nieuport 17 with its squadron insignia of the Star of David.
[5] After failing to score any further aerial victories, Fyodorov was reassigned to instructor duty, this time at Sevastopol.
By the time Fyodorov was discharged, Russia had quit fighting and was engaged in the Russian Civil War.
When they had returned to Russia, they had been promised a departure travel allowance of 775 rubles for the pilot and 300 for the mechanic; it is unknown if they collected this.
After a wait for reassignment,[5] Fyodorov joined Escadrille 89, a SPAD squadron,[2] in June 1918, and became a temporary Lieutenant on 9 August 1918.
On 12 August, he was honored with an award of the Legion d'honneur: the citation read: "Magnificent example of patriotism, bravery, and sense of duty.
Wounded in the infantry, then transferred to the aviation service, distinguished himself by his bravery and his brilliant combats during which he shot down four enemy planes.
After the campaigns of Romania and Russia, returned to the French front being always in combat a model of spirit, courage, and tenacity.
"[5] Escadrille 89 was one of the French squadrons whose operational control was assigned to American General John J. Pershing's command, the First Army.
On 9 October 1918, while on a bomber escort sortie, Fyodorov shot down a German fighter for his fifth accredited victory.
[6] An award citation of 7 November 1918 eloquently outlined his wartime service: "Victor Federov, Sous-Lieutenant in the Foreign Regiment, pilot in the squadron Spa.89, courageous officer.
On October 16, 1918, attacked by three Fokkers and wounded during the combat, successfully brought back his bullet-riddled plane to our lines.