Fedutenko was born in Rakitnoye village. Both her parents worked at a sugar factory. She participated in skiing, skating and horse riding. Fedutenko later worked at the same factory, and continued her education at the factory's apprenticeship school after receiving seven years of incomplete secondary education. In that period, she participated in an aircraft modelling hobby group. She enrolled in the Tambov Civil Aviation Flying School at the age of 18. Between 1935 and 1941, Fedutenko was a civil aviation pilot. By the time of the German invasion she had mastered several aircraft types and her flying time was measured in thousands of hours.
From June 23, 1941 to October 15, 1941 she flew the Polikarpov R-5 biplane with the Kiev Special Group of the Civil Air Fleet – an auxiliary unit established by Soviet civil aviation authorities. She flew supply and liaison missions in support of the fighting troops, including the evacuation of 150 wounded soldiers, and the transportation of the Red Army Stavka representatives, among others. During these missions she occasionally had to evade enemy fighter attacks. By December 1942 Fedutenko converted to flying the Petlyakov Pe-2 medium bomber after graduating from training courses at the Engels Military Aviation School for Pilots. From January 1943, she flew combat missions for the 587th Bomber Aviation Regiment, one of the three female combat flying units established by Marina Raskova. On May 26, 1943, during the Kuban air battles, Fedutenko received a head wound from an anti-aircraft gun shell fragment just before dropping bombs on heavily defended German artillery positions near the village of Kiyevskoye, Krasnodar Krai. Despite her severe wound, she retained full control of her aircraft and command of her flight, and was able to stay in formation, ensuing the eventual destruction of the target. Fedutenko then conducted a flak evasion maneuver, preventing the loss of aircraft and aircrew in her command. By March 1945 Fedutenko had flown 56 missions on the Pe-2, in 20 of which in she was a flight leader, leading 3 aircraft, in 25 a squadron leader, leading 9 aircraft, and on 2 occasions led a combined division of six squadron V-formations following each other in a column with squadrons drawn from the different regiments of the same division with a total strength of 54 aircraft. In one of these occasions she was not assigned as the leading pilot of the division formation, but when the leader was downed on approaching the target, she took the lead and ensued the successful accomplishment of the mission. Fedutenko's command considered her performance as a pilot and commander to be efficient and instrumental to the destruction of enemy assets. On March 14, 1945, Fedutenko's superior recommended that she be awarded the title of Hero of Soviet Union for "the exceptional services she rendered for the Motherland showing valour and heroism". She was officially bestowed the title on August 18. In addition, she received the Order of Lenin, the Order of the Red Banner, the Order of Patriotic War, First Class, and many medals.
