През 1983 г. Надежда сключва брак с Камен Михайлов и имат две дъщери - Нина Михайлова и Виолета Михайлова. През 1999 голямата ѝ дъщеря заминава да учи в колеж в [[Швейцария]].<ref>{{cite news |title= Децата на първенците ни литнаха на Запад |url= http://www.bgnews.bg/show_story.html?issue=70458519&media=10190876&class=70443479&story=89221045 |publisher= Вестник "Сега" |date= 1999-01-30 }}</ref> През 2006 г. Надежда и Камен се развеждат.<ref>{{cite news |title= Надежда изпя: Развод ми дай |url= http://www.standartnews.com/bg/article.php?d=2007-01-06&article=173546 |publisher= Вестник "Стандарт" |date= 2007-01-06 }}</ref>
На 3 октомври 2009 Надежда Михайлова се омъжва за [[Светлин Нейнски]]. Евродепутатката и бизнесменът са сключили граждански брак в посолството на България в [[Мадрид]].
