Born in Porfiryevka, Crimea in USSR, Nelyubov was a captain and pilot in the Soviet Air Force. He was selected as one of the original 20 cosmonauts on March 7, 1960 along with Yuri Gagarin. The following year, six of the original twenty were evaluated for assignment on Vostok flight crews between January 17 and 18; Gagarin, Titov, and Nelyubov were considered the top three candidates. For Vostok 1 Nelyubov was chosen as second backup for Gagarin and presumably first backup for Vostok 2 for Titov in April and August 1961 respectively. For the dual launches of Vostok 3 and Vostok 4, Nelyubov was again chosen as a backup for Andrian Nikolayev and Pavel Popovich.
On March 27, 1963, Nelyubov, Ivan Anikeyev and Valentin Filatyev were arrested for drunk and disorderly conduct by the military security patrol (комендатура) at Chkalovskaya station. According to reports, the duty officer agreed to ignore the whole incident and not send the report if Nelyubov apologized, but he refused, and the matter was reported to the authorities. Because there were previous incidents, all three were dismissed from the cosmonaut corps on April 17, 1963, though officially not until May 4, 1963. Pavel Popovich, secretary of the party organization, tried to resolve the situation by calling a party meeting where Nelyubov was once again invited to apologize to the patrol chief and to the other cosmonauts, but he again refused. He was dismissed, never having completed a space mission.
Following dismissal he went back to flying interceptors in Far East but fell to drinking and depression. He died on February 18, 1966. While drunk, he stepped in front of a train near the Ippolitovka station, northwest of Vladivostok. It was officially ruled a suicide. To protect the image of the space program, efforts were made to cover up the reason for Nelyubov's dismissal and his following suicide. His image was airbrushed out of the "Sochi Six" photo which showed the top members of the original class of Soviet cosmonauts. This airbrushing led to speculation about "lost cosmonauts".