Nadeschda Kadyschewa wurde am 1. Juni 1959 im mordwinischen Dorf Gorki geboren. Sie wuchs mit vier Schwestern auf und verlor im Alter von zehn Jahren ihre Mutter. Da die zweite Ehefrau des Vaters Kinder mitbrachte, mussten ihre Schwestern das Haus verlassen. Kadyschewa verließ nach acht Jahren die Schule und begann als Weberin zu arbeiten. Im Alter von 19 Jahren bestand sie die Aufnahmeprüfung der Ippolitow-Iwanow-Musikschule. Im gemeinsamen Hostel lernte sie Alexander Kostjuk kennen, der das Gnessin-Institut Moskau besuchte. Im dritten Jahr wurde Kadyschewa angeboten, im Rossijanotschka-Ensemble von Moskonzert zu arbeiten. Sie wechselte an das Gnessin-Institut und besuchte dort die Klasse von Nina Meschko.
Im Jahr 1983 heiratete Kadyschewa Alexander Kostjuk und wurde im folgenden Jahr Mutter eines Sohnes. Mit Kostjuk gründete sie 1988 das Ensemble «Золотое кольцо» (Solotoje kolzo; Goldener Ring) und wurde dessen Solistin. Sie traten überwiegend im Ausland auf und wurden erst nach 1993 in Russland bekannt, nachdem sie mit dem Studio Sojus eine Zusammenarbeit vereinbart hatten. Drei Jahre später gewann Kadyschewa mit Solotoje kolzo die nationale Auszeichnung Goldenes Grammophon. Mit ihren Duettpartnern gewann sie diese Auszeichnung auch 2004 und 2008. Mit Al Bano nahm sie 2014 die SingleFelicità auf. Zu ihren Genres gehören Volksmusik, Schlager und Chanson.
