Родена е на 9 август 1962 г. в София. Учи в 127 СОУ "Иван Денкоглу". Завършва испанския профил на 9-та Френска езикова гимназия "Алфонс дьо Ламартин".

Завършва българска филология (1985).

Работи като учител по испански език.

1986 - 1988 г. работи като журналист на свободна практика. Живее и в Египет, където тогавашният ѝ съпруг е зам.-шеф на външнотърговското предприятие „Техноекспорт”. Ч

Член на Съюза на преводачите в България. Превежда поезия от испански и английска литература.

Започва политическата си кариера в Радикалдемократическата партия в България. Началник на отдела за международни отношения на РДП от 1990 до 1991 г.

1991 г. - директор на пресцентъра на СДС по време на предизборната кампания за 36-то Народно събрание.

1991-1992 г. - говорител на правителството на СДС начело с Филип Димитров  и началник на пресцентъра на Министерския съвет.

1991-1994 г. - директор на пресцентъра на СДС.

Специализира външна политика и връзки с обществеността в Харвардския университет и към Конгреса на САЩ.

Депутат в 37-ото Народно събрание;  член на Парламентарната комисия по външна политика; участва и в българската делегация в Съвета на Европа.

1995 г. - член на Националния изпълнителен съвет  и зам.-председател на СДС. Председател на Комисията по парламентарни и обществени връзки на ПАСЕ от януари 1997 г. Председател на комисията от януари 1997 г.

1997 г. - зам.-председател на СДС, депутат в 38-ото Народно събрание  Председател на Съвета по евроинтеграция и национален координатор на програма ФАР от май 1997 г.

Министър на външните работи в правителството на Обединените демократични сили, оглавявано от Иван Костов.

През февруари 1999 г. е избрана  с 3-годишен мандат за зам.-председател на Европейската народна партия на XIII конгрес на ЕНП в Брюксел. Михайлова е първият източноевропейски политик, заемащ този пост. За нейния избор силно се е застъпил испанският премиер Хосе Мария Аснар.

Загубва поста на външен министър след парламентарните избори през юни 2001 г., когато на власт идва правителството на Симеон Сакскобургготски.

Избрана за депутат в 39-ото народно събрание. Председател на парламентарната група на ОДС.

2003 г. - Избрана за председател на СДС на ХІІІ Национална конференция на СДС на 11 март 2002 г. (През 2004 г. Иван Костов с група народни представители напуска СДС и парламентарната му група, а впоследствие основава конкурентната дясна партия Демократи за силна България.)

През 2004 г. Надежда Михайлова става председател на Института за демокрация и стабилност в Югоизточна Европа. От 2006 г. е член на международния консултативен съвет към Democracy Coalition Project и член на консултативната група за Кръгла маса на лидерите на южните държави към Съвета за южно сътрудничество.

2005 - СДС, чийто председател е Н. Михайлова, участва в парламентарните избори през юни за 40 НС в рамките на новосъздадената коалиция ОДС (СДС, Гергьовден, Демократическа партия, БЗНС - Янев), партия на ромите ДРОМ.

Избрана за народен представител от София 23 МИР.

Ноември 2005 - губи лидерското си място в СДС (на този пост е избран Петър Стоянов). На 30 ноември обявява  създаването на нова фракция "Дясна алтернатива" в рамките на партията, която да бъде учредена на 11 декември в Плевен. Очакването е членовете на фракцията да споделят идеята, че СДС трябва да е категорична опозиция на управляващите. Основно несъгласие на Михайлова с политиката, следвана от П. Стоянов, е търсенето на сближаване с НДСВ.

11 декември 2005 - пренебрегва призива на редица известни привърженици на СДС да не се пристъпва към това и участва във учредяването на Съюз "Дясна алтернатива" в СДС. Става член на националното му ръководство.

От 2007 г. е председател на Съюза на малките и средни предприятия в България (СМСП). През 2007 г. е избрана за вицепрезидент на Съюза на малките и средни предприятия към Европейската народна партия.

Кавалер на Националния орден на Почетния легион - удостоена с най-високото държавно отличие на Франция с указ на президента на Републиката Никола Саркози за приноса й в развитието на двустранните отношения и общата европейска кауза. Отличиетго й е връчено на 7 октомври 2008 в посолството на Република Франция в София от посланика Етиен дьо Понсен.

2009 - избрана за депутат в Европейския парламент в групата на Европейската народна партия (Християндемократи).

2013 - оглавява новосъздадената партия "Синьо единство".

2015 - назначена за посланик на Р България в Турция.

2020 - Министерският съвет одобрява кандидатурата й за поста на Генерален секретар на Организацията за Черноморско икономическо сътрудничество за периода 1 юли 2021 - 30 юни 2024 г.

Ползва английски, испански и руски.

Омъжена, има две дъщери.

През 2009 година се омъжва повторно и взема фамилията на новия си съпруг, така вече е известна като Надежда Неински.

Михайлова е обвинявана от някои в клиентелизъм във връзка със съмнителното участие на бившия й съпруг, Камен Михайлов, в придобиването през 1998 г. на "Автотранссервиз" - бившите гаражи на ЦК на БКП. Известна е и с произнесената от нея пред ловешките активисти на СДС фраза "Нахранете журналистите!"