Nyesztyerenko kisgyermekként gramofonon hallgatta a kor "sztárjait", akik közül minden idők egyik legnagyobb basszus-énekese, az orosz Fjodor Saljapin és az amerikai Paul Robeson volt rá nagy hatással. A zene mellett másik nagy szerelme az építészet volt, meg is szerezte az építészmérnöki diplomát, de ezzel párhuzamosan elvégezte a leningrádi Rimszkij-Korszakov konzervatóriumot is. Végül a zene mellett döntött, s minden erejét az éneklésre összpontosította.

1965-ben szerződtette a leningrádi Mariinszkij színház, majd 1970-ben megnyerte a moszkvai nemzetközi Csajkovszkij énekversenyt. Egy év múlva már a moszkvai Nagyszínház vezető énekese volt, élete legboldogabb napjának máig 1972. június 22-ét tartja, amikor a Bolsoj színpadán Glinka Ruszlán és Ludmilla című operájában debütált. Nyesztyerenko több mint 3500 koncertet adott (karrierje csúcsán évente 250-et), 70 lemezfelvételt készített, 80 opera vezető szerepét énekelte, több mint húszat eredeti nyelven. Kamaraénekesként és oratóriumokban is fellépett, repertoárja mintegy ötszáz dalt, népdalt és románcot ölel fel. Hangját megcsodálhatta a New York-i Metropolitan, a londoni Covent Garden, a Bécsi Állami Operaház közönsége, Jelena Obrazcovával ők voltak a milánói Scala első orosz énekesei.

Élete első külföldi fellépése Magyarországon volt 1970-ben, és saját bevallása szerint Olaszország után talán itt lépett föl a leggyakrabban. 1981-ben Ferencsik János vezényletével vette fel A kékszakállú herceg várát, 1985-ben első külföldiként ő énekelte Budapesten magyarul Bartók operáját. Tavaly a Szent Efrém Férfikar vendégeként a Máriapócsi Kegytemplomban és a Szent István-bazilikában lépett fel, Magyarországon ekkor először énekelt koncerten szláv egyházzenét (az alábbi videón ennek a koncertnek a pillanatait idézzük fel). A kiváló basszista 1973 óta foglalkozik orosz liturgikus zenével, s már 1985-ben egyházzenei lemeze jelent meg a moszkvai állami kamarakórussal, a felvételek Budapesten készültek a magyar és az orosz lemezkiadó együttműködésében.

Nyesztyerenko leghíresebb szerepei az orosz klasszikus operákhoz fűződnek (Glinka: Ruszlán és Ludmilla, Ivan Szuszanyin, Muszorgszkij: Borisz Godunov, Ivan Hovanszkij, Borogyin: Igor herceg), de kiemelkedőt nyújtott Mozart A varázsfuvolájának Sarastrójaként, valamint olyan operák főszereplőjeként is, mint Verditől az Attila, a Nabucco és a Don Carlos, Rossinitől A sevillai borbély vagy Gounod Faustja. Részese volt Sosztakovics és számos más orosz kortárs zeneszerző ősbemutatóinak, több operát kifejezetten az ő hangjára írtak.

A szakmai közönség elsősorban lenyűgöző eleganciáját, pontosságát, szenvedélyességét, kivételes muzikalitását emeli ki. Nyesztyerenko zenepedagógus is, 1975-1993 között a moszkvai Csajkovszkij Konzervatóriumban, 1993-tól tíz évig a bécsi konzervatóriumban tanított (lakóhelye is az osztrák főváros), két könyve és több mint 200 cikke jelent meg. Magyarországon is több alkalommal tartott énekes mesterkurzust, s több fiatal magyar tehetség útját egyengette, a budapesti Zeneakadémia tiszteletbeli professzora. Karrierje során 12 nyelven énekelt, németül, franciául és angolul beszél, tanítás közben négy nyelvet (orosz, német, francia, angol) használ, s amikor A kékszakállú herceg várát gyakorolta, magyarul is tanult. A művész hobbija a teaféleségek gyűjtése.

A 2012-es év során a Fideliónak is volt alkalma interjút készíteni a művésszel. A Szent Efrém Férfikarral közös koncertje egyik próbája után beszélgettünk vele, és kérdésünkre azt is elárulta, gyakorol-e még. Az Opera Magazin legújabb számának előszavában pedig azt is elárulta, hogy 2013-ban is lesz budapesti fellépése: a Magyar Állami Operaházban orosz dalestet ad, és énekkurzust is tart. Ebből az előszóból idézünk az alábbiakban: 

"Évtizedeket kell számba venni ahhoz, hogy felidézzem mindazt a rengeteg élményt, amely Magyarországhoz köt. Mindig nagy öröm volt Budapestre látogatnom, pedig a Kékszakállú szerepe magyar szöveggel elsőre ijesztő feladat, még lemezstúdióban is az. [...] Magyarország: szerelem. Nemcsak Bartók miatt - rá  különösen büszkék lehetnek! -, de a vendégszeretet, az orosz kultúra értő tisztelete miatt is. (És voltam én már hun, nemcsak magyar: Verdi Attilájaként!) S azok az esték az Állami Operaházban... éppoly kedves emlékeim, mint a Met, a Scala, a bécsi Opera vagy a Bolsoj színpadán töltöttek."

Kedves Maestro, Isten éltesse még sokáig!