Родилась 1 июня 1959 г. в дер. Горки (Лениногорский район Татарской АССР, ныне Республика Татарстан).
Училась в школе-интернате в гор. Бугульме (Татарская АССР, ныне Республика Татарстан). В 14 лет переехала к сестре в Подмосковье, начала работать на прядильной фабрике "Красная поляна" (гор. Лобня). Участвовала в творческой самодеятельности.
В 1978-1979 гг. Надежда Кадышева училась на подготовительном отделении Московского городского музыкального училища им. М. М. Ипполитова-Иванова (МГМУ; ныне Государственный музыкально-педагогический институт им. М. М. Ипполитова-Иванова). Поступила в МГМУ, затем перевелась в Государственный музыкально-педагогический институт им. Гнесиных (ныне Российская академия музыки им. Гнесиных). Окончила его в 1983 г. по вокальному классу профессора Нины Мешко.
С начала 1980-х гг. выступала в составе квартета народной песни "Россияночка" при Москонцерте.
В 1988 г. Надежда Кадышева стала солисткой эстрадного ансамбля "Золотое кольцо", созданного ее супругом Александром Костюком. Выступает в его составе по настоящее время. Основу репертуара Надежды Кадышевой и "Золотого кольца" составляют народные песни и композиции, написанные современными авторами (Виктор Пеленягрэ, Владимир Степанов и др.). На протяжении карьеры исполнительница записала более 20 музыкальных альбомов, гастролировала во многих городах России и зарубежья.
Народная артистка РФ (1999).
Почетный гражданин Бугульмы (2000).
Четырехкратная обладательница российской музыкальной премии "Золотой граммофон" (1996, 1999, 2004, 2008).
Замужем. Супруг - заслуженный артист РФ, создатель и руководитель ансамбля "Золотое кольцо" Александр Костюк (род. 1958). Сын - Григорий Костюк (род. 1984, концертный директор).
Жизни и творчеству певицы посвящен документальный фильм "Родовое проклятие Надежды Кадышевой" (2008, режиссер Алексей Грицаенко).