In May that year he entered the Red Army, and in February 1943 he graduated from the Voroshilov Military Aviation School of Pilots.

[2] Having graduated from training in February, Nedbaylo arrived at the Eastern Front of World War II in March.

On 5 February 1944 while returning from a target over Nikopol in poor weather, they got into a mid-air collision with another plane, leaving Nedbaylo seriously injured.

After Malyuk sustained a serious head injury on mission with another pilot, Nedbaylo began flying with Dmitry Matveev as his gunner.

[3] On 26 June Nedbaylo successfully led a mission that resulted in the destruction of Axis trains in Orsha-Tolochin, Vitebsk.

[4] During the war he executed a belly-landing, sustained serious damaged to his aircraft from enemy fire, returned to the airbase with half the tail of his plane gone, and was shot down three times.