Идеята за изграждането ѝ е на парижкия епископ Морис дьо Сюли, който финансира проекта със средства, получени от духовенството, краля, благородниците, дори и от дребната буржоазия. в продължение на близо два века няколко поколения архитекти и работници влагат труд по нея. Катедралата е напълно завършена през 1345 г. Тя е едно от най-великите постижения на готическата архитектура.
По не съвсем сигурни данни от летописеца Жан дьо Сен-Виктор в неговата Memoriale Historiarum (Исторически мемоари), в периода между 24 март и 25 април 1163 г. папа Александър III полага първия камък в присъствието на крал Луи VII. В сегашното състояние на информацията, традиционната дата на началото на работата на Нотърдам се счита 1163 г. Основната работа се извършва под ръководството на епископ Морис дьо Сюли и неговият наследник Одон Сюли (нямат роднинска връзка).
На 16 декември 1431 г. детето-крал Хенри VI от Англия е коронован за крал на Франция в Нотърдам, на десет години, защото традиционната църква на Реймската катедрала е под френски контрол.
По време на Ренесанса готическият стил вече не е на мода, вътрешните колони и стените на „Света Богородица“ са покрити с гоблени.
През 1548 г. бунтовниците хугеноти увреждат някои от статуите, считайки ги за идолопоклоннически.
Фонтанът в парка е добавен през 1625 г., за да осигури на парижани течаща вода.
Крал Луи XIV, по настояване на баща си, Луи XIII, решава през 1699 г. да направи значителни изменения в катедралата. Той възлага на Робер дьо Кот обновяването. Кот заменя старата с разкошна нова позлатена ограда от ковано желязо, отваря хора и деамбулаторията и сваля гробниците в кораба. Произведени са нови мебели, както и настоящият висок олтар, изобразяващ Луи XIV и Луи XIII на колене пред Пиета. През 1709 г. Антоан дьо Ла Порт поръчва на Луи XIV шест картини, изобразяващи живота на Дева Мария за да украси хора. По същото време Шарл де Ла Фос рисува своето „Поклонение на Маговете“, сега в Лувъра. Луи Антоан дьо Ноай, архиепископ на Париж, обширно модифицира покрива през 1726 г., обновявайки рамката и премахвайки гаргойлите с оловни улуци. Ноай също укрепва опорите, галериите, терасите и трезорите. През 1756 г. каноните на катедралата решават, че вътрешността му е твърде тъмна. Средновековните витражи, с изключение на розетните прозорци, са отстранени и заменени с обикновени, бели стъкла.
През февруари 1791 г., чрез поредица от постановления на Учредителното събрание по предложение на кметството на Париж, катедралата Нотърдам в Париж става седалище на енорията на града чрез прехвърляне на правомощия, упражнявани дотогава до малки църкви на острова.
По време на Френската революция, много актове на вандализъм са извършени в катедралата. През това време много от съкровищата на катедралата са унищожени или ограбени. Двадесет и осемте статуи на библейските царе, разположени на западната фасада, сгрешени за статуи на френски крале, са обезглавени по личната разпоредба на Робеспиер. 21 от 28-те оригинални глави и много други фрагменти са открити през 1977 г., като тези глави сега са в музея на Клуни. Всички големи статуи на порталите също са били унищожени, с изключение на Богородица. За известно време богинята на свободата заменя Дева Мария на няколко олтара. Култът на разума преименувана с указ Парижската Света Богородица на 10 ноември 1793 г., празника на свободата, в Храм на Разума[17]. Този култ е организиран от Пиер-Гаспард Шомет, а главният олтар е превърнат в олтар на бога Разум. В края на ноември същата година католическото богослужение е забранено в Париж. След това катедралата се преобразува в склад за храна.
През юли 1801 г. новият владетел на Франция, Наполеон Бонапарт подписва споразумение за възстановяване на църквата. Той е официално преместен на 18 април 1802 г. На 2 декември 1804 г. Наполеон и съпругата му Жозефин, заедно с папа Пий VII, са короновани за император и императрица на Франция. Катедралата е и мястото на брака на Наполеон с Мария-Луиза Австрийска през 1810 година.
„Света Богородица“ функционира в началото на 19 век, но е наполовина разрушена отвътре и очукана навсякъде. През 1831 г. романът „Парижката Света Богородица“ от Виктор Юго, публикуван на английски език като „Гърбушкото от Нотр Дам“, има огромен успех и привлича вниманието към катедралата. През 1844 г. крал Луи-Филип нарежда църквата да бъде възстановена. Поръчката за възстановяването е спечелена от двама архитекти, Жан-Батист-Антоан Ласус и Йожен Виолет-льо-Дюк, който тогава е само на 31 години. Те ръководят голям екип от скулптори, стъклари и други занаятчии, които преработват, работейки от рисунки или гравюри, оригиналната декорация, или ако няма модел, добавят нови елементи, които чувстват, че са в духа на оригиналния стил. Те правят по-висока и по-богато украсена реконструкция на оригиналния шпил (включително статуя на свети Тома), както и добавянето на скулптури на митични същества. Възстановяването отнема двадесет и пет години.
По време на Освобождението на Париж през август 1944 г. катедралата понася някои незначителни щети от куршуми. Част от средновековното стъкло е повредено и заменено със стъкло с модерни абстрактни дизайни. На 26 август в катедралата се провежда специална меса за празнуване на освобождението на Париж от германците, като на него присъстват генералите Шарл дьо Гол и Филип Льоклер дьо Отклок.
През 1963 г. по инициатива на министъра на културата Андре Малро и по повод 800-годишнината на катедралата, фасадата е почистена от наслоените с векове сажди и мръсотия, възстановявайки я до оригиналния ѝ белезникаво бял цвят.
Художествените произведения, реликви и други антики, съхранявани в катедралата, включват предполагаемия трънен венец, който Исус носи преди разпятието му и част от кръста, на който е бил разпънат, орган от 13 век, прозорци с витражи и бронзови статуи на 12-те апостоли.
Комплектът от четири камбани от 19 век в северните кули е разтопен и преработен в нови бронзови камбани през 2013 г., за да се отпразнува 850-годишнината на сградата. Те са създадени, за да пресъздадат звука от оригиналните камбани на катедралата от 17 век. Въпреки реставрацията от 90-те години на миналия век, катедралата продължава да показва признаци на влошаване, което кара националното правителство да предложи нова програма за обновяване в края на 2010 г. Целият ремонт се очаква да струва 100 милиона евро, което архиепископът на Париж планира да набере чрез средства от националното правителство и от частни дарения. Реновирането на шпила на катедралата от 6 милиона евро започва в края на 2018 г. и продължава през следващата година, което изисква временно премахване на медни статуи на покрива и други декоративни елементи дни преди пожара през април 2019 г.
На 15 април 2019 г. в 18:50 местно време избухва пожар на покрива на катедралата, причинявайки срутването на шпила и покрива. Първоначално размерът на щетите е неизвестен, както и причината за пожара. Предполага се, че пожарът е свързан с текущите ремонтни дейности. Говорител заявява, че сводът на сградата също е застрашен. Според френските власти, катедралата е била само на „15 до 30 минути“ от пълно унищожение вследствие на структурните повреди, толкова тежки, че вероятно биха довели до падането на сградата.
Пожарникарите успяват да запазят фасадата, кулите, стените, опорите и стъклописите. Великият орган, който има над 8000 тръби и е построен от Франсоа Тиери през 18 век, също е спасен, но е претърпял щети от водата. Поради текущите реставрационни работи, медните статуи върху шпила са отстранени преди огъня. Каменният свод, който оформя тавана на катедралата, има няколко дупки, но иначе е непокътнат.
От 1905 г. френските катедрали са собственост на държавата, която ги стопанисва. В случай на щети при ремонт някои разходи могат да бъдат възстановени от застрахователи, ако се установи, че са причинени от работещите на обекта. Френска застрахователна компания осигурява застрахователно покритие за две от фирмите, работещи по възстановяването на Нотърдам. Същата компания е застраховала и някои от реликвите и произведенията на изкуството в катедралата.
Президентът Еманюел Макрон казва, че около 500 пожарникари са помогнали за борбата с пожара. Един пожарникар е сериозно ранен и двама полицейски служители са наранени по време на пожара. Той обещава, че Нотр Дам ще бъде възстановена, и призовава работата да бъде завършена до пет години. Организиран е и международен архитектурен конкурс за преустройство на покрива и шпила.
След трагичния инцидент френските власти, бизнесмени, обществени организации и голяма част от обществото на Франция и Европа, започват да събират средства за възстановяването на емблематичната катедрала. Към 23:00 часа на 16 април, даренията събрани за ремонта на катедралата наброяват около 700 милиона евро. Към 18 април даренията за „Парижката Света Богородица" достигат 1 милиард евро. Въпреки това все още няма точна оценка за разходите за възстановителните дейности.