Nesterenko's first profession was architecture, and in fact he graduated from the Engineering and Construction Institute in Leningrad. But he was called to music, and he studied under Vasily Lukanin at the Leningrad Conservatory. At his last year at the conservatory (1965) Nesterenko was invited to sing at Leningrad's Maly Opera Theatre and after graduation joined the famous Mariinsky Opera and Ballet Theatre. He won the gold medal at the 4th Moscow International Tchaikovsky Competition, which gave him entrée to Moscow's Bolshoi Theatre.
Altogether Nesterenko has sung over 80 leading bass parts and performed 21 operas in their original languages. He performed the main parts in operas by Glinka, Mussorgsky, Tchaikovsky and Borodin, and was the first to perform many works by Shostakovich, Sviridov and Taktakishvili.
Nesterenko's enormous repertoire ranges from deep bass to baritone parts in operas by classical Russian and West-European composers. His finest role is frequently considered to be Tsar Boris in Mussorgsky's opera Boris Godunov, which won him the "Golden Viotti" medal in Italy in 1981.
The stages on which Nesterenko has performed include many of the world's best and most prestigious ones, such as the Metropolitan Opera, Covent Garden, the Vienna State Opera and La Scala. He has been awarded the highest Austrian, Italian, German and Russian awards for his singing. He is the winner of the Giovanni Zenatello Prize "For an outstanding embodiment of the central character in the opera Attila by Verdi". He is the winner of the Chaliapin Prize of the Creativity Academy and the holder of many other titles and awards.
Nesterenko has recorded about 70 records and discs, including 20 operas in full. He is also an outstanding chamber singer with a subtle taste, expressiveness and sense of style.
Latterly he has also become known as an outstanding teacher. He teaches at the Moscow Conservatory and the Higher Music School in Vienna. Nesterenko is the author of two books - My Way of Working with Singers and Reflections on My Profession - and is the author of over 200 printed articles. In addition he is one of the most experienced music competition jurors in the world.