Родилась 15 мая 1956 г. в Чебоксарах (Чувашская АССР, ныне Чувашская Республика) в семье Василия Петровича и Марии Ильиничны Павловых. Ее отец работал рентгенотехником в больнице. Мать была воспитательницей в детском саду.
В середине 1960-х гг. Надежда Павлова посещала занятия в хореографическом кружке при чебоксарском Доме пионеров.
В 1974 г. окончила Пермское государственное хореографическое училище по балетному классу педагога Людмилы Сахаровой, в 1984 г. - балетмейстерский факультет Государственного института театрального искусства им. А. В. Луначарского (ныне Российский институт театрального искусства - ГИТИС, Москва).
В 1975-2000 гг. Надежда Павлова являлась солисткой балетной труппы Государственного академического Большого театра. Среди исполненных ею партий: Жизель в одноименном балете Адольфа Адана, Маша в "Щелкунчике" и Одетта-Одиллия в "Лебедином озере" Петра Чайковского, Китри в "Дон Кихоте" и Никия в "Баядерке" Людвига Минкуса, Фригия в "Спартаке" Арама Хачатуряна, Джульетта в "Ромео и Джульетте" Сергея Прокофьева, Сильфида в одноименном балете Германа Левенскольда. Постоянным сценическим партнером балерины был Вячеслав Гордеев.
В 1992-1994 гг. руководила московским Театром балета Надежды Павловой, в 1995 г. была художественным руководителем труппы "Ренессанс-Балет".
В 1998-1999 гг. как приглашенная артистка выступала в постановках труппы "Русский балет".
В 2000 г. Надежда Павлова окончила танцевальную карьеру. В том же году работала педагогом-репетитором балетного театра ГИТИСа под руководством Виталия Ахундова.
С 2009 г. по н. в. - балетмейстер-репетитор в Государственном академическом театре классического балета под руководством Наталии Касаткиной и Владимира Василёва.
С 2013 г. по н. в. Надежда Павлова является балетмейстером-репетитором Большого театра.
Исполняла роли в фильме-сказке "Синяя птица" (1976, режиссер Джордж Кьюкор, СССР - США) и в детективном фильме "Сицилианская защита" (1980, Игорь Усов).
Народная артистка СССР (1984).
Награждена орденом "Знак Почета" (1976).
Лауреат премии Ленинского комсомола (1975).
Обладательница I премии Всесоюзного конкурса балетмейстеров и артистов балета (1972, Москва), Гран-при II Международного конкурса артистов балета (1973, Москва).
Замужем во второй раз. Супруг - врач-психотерапевт Константин Павлов (род. 1945, взял фамилию жены). Первым мужем Надежды Павловой был народный артист СССР Вячеслав Гордеев (род. 1948).