Antigament els celtes havien celebrat en aquest lloc les seves cerimònies. Més tard, els romans erigirien un temple de devoció al déu Júpiter. També en aquest lloc va existir la primera església cristiana de París, la Basílica de Saint-Etienne, projectada per Khildebert I als voltants de l'any 528 dC. La façana occidental era a uns quaranta metres més a l'oest de l'actual façana de Notre-Dame i tenia una amplada lleugerament més petita, mesurava 36 metres. Aquest edifici tenia una longitud de 70 metres, és a dir, una mica més de la meitat de la longitud de la catedral actual. Files de columnes separaven una nau i quatre naus laterals.

Al costat nord de la catedral de Saint-Etienne hi havia un baptisteri.

En substitució d'aquesta obra, sorgeix una església romànica que restarà fins a l'any 1163, quan es dona l'impuls definitiu a la construcció de la catedral actual.

L'any 1160, el bisbe Maurice de Sully considera l'església (de San Esteve) poc digna, i la mana enderrocar. El gòtic inicial, amb les seves innovacions tècniques li permeten formes fins aleshores impossibles de fer. Durant el regnat de Lluís VII, i amb el seu suport, aquest projecte és beneït per totes les classes socials interessades en la creació d'un símbol de seu nou poder. La construcció s'inicia l'any 1163, encara hi ha dubtes quant a la identitat de qui hauria posat la primera pedra, si el bisbe Maurice de Sully o el papa Alexandre III. Al llarg del procés (la construcció, incloent-hi modificacions, durà fins a mitjan segle xiv) foren diversos els arquitectes que participaren en el projecte, justificant aquest factor les diferències estilístiques presents en l'edifici.

Primer període: 1163 - 1250  Tall esquemàtic de la nau principal amb les seves dues naus laterals d'igual altura i les seves tribunes tal com es representava el 1220-1230.1163-1182 Construcció del cor i els seus dos deambulatoris. 1182-1190 Construcció dels últims quatre intercolumnis de la nau, els passadissos i galeries. La construcció de la nau va començar el 1182, després de la consagració del cor. Alguns fins i tot pensen que el treball va començar el 1175. El treball es va aturar després del quart intercolumni, deixant la nau inacabada. 1190-1225 Construcció de la base de la façana i dels dos primers intercolumnis de la nau. El 1208 es va començar la façana. A partir d'aquest any, es varen construir i decorar les portes. La planta del rosetó data de 1220-1225. La construcció dels primers intercolumnis de la nau va ser represa el 1218 amb la finalitat de neutralitzar l'empenta de la façana. 1225-1250 Part superior de la façana i les dues torres. L'ampliació de les finestres superiors (supressió de petits rosetons) per fer front a la foscor (cap al 1230). Al mateix temps el sostre de les golfes de les tribunes de l'àtic se substitueix per terrasses, i nous arcbotants amb canaletes permetent l'evacuació d'aigües pluvials de la part superior de l'edifici. Es construïren les capelles laterals de la nau entre els pilars dels arcbotants. L'any 1240 es va acabar la torre sud i aquest mateix any es va abandonar la idea de dotar les torres d'una agulla. El 1250, es va finalitzar la construcció de la torre nord. En aquest moment la catedral està de fet acabada i plenament operativa. Estam en el regnat de sant Lluís. Les fases posteriors seran ampliacions, millores, reparacions i modificacions de vegades molt importants.Segon període: 1250 - meitat del segle xiv

En aquesta època, es va trobar que els portals del transsepte, construïts en estil romànic, molt server, contrastaven amb la gran façana gòtica ricament adornada a l'estil de l'època. La reconstrucció de les parts romàniques va ser decidida ràpidament pel bisbe Renaud de Corbeil (1250-1268).

Sabem els noms dels contractistes que se succeïren durant aquest període. Es tracta de: Jean de Chelles, Pierre de Montreuil, Pierre de Chelles, Ravy Jean, Jean Bouteiller i Raymond du Temple.

Jean de Chelles va procedir a la prolongació del transsepte, primer a la part nord (1250), després la sud. A ell es deu la façana nord del transsepte i el seu magnífic rosetó. Després de la seva mort el 1265, el treball en el braç sud del transsepte va ser acabat per Pierre de Montreuil a qui devem la paret sud del transsepte i el seu, igualment bonic, rosetó. Va morir el 1267. Pierre de Montreuil també havia completat les capelles i la porta vermella. De la mateixa manera, va començar a reemplaçar els contraforts del cor.

El seu successor, Pierre de Chelles, va fer la part superior del cor i va començar les capelles de la capçalera el 1296.

Aquestes capelles les va acabar Jean Ravy, que va ser director del projecte des del 1318 al 1344. Jean Ravy va començar la construcció dels admirables contraforts del cor d'una amplada de 15 metres. També va començar a fer l'element de tancament del cor.

El 1344, el seu nebot, Joan Bouteiller, el va succeir fins al 1363.

Després de la seva mort, el seu adjunt, Raymond du Temple, va completar el seu treball, incloent-hi el magnífic element de tancament del cor.

Els segles xvii i xviii  L'altar de Notre-Dame al segle xviii
dibuix de Jean-Baptiste Scotin

A la fi del segle xvii, d'acord amb els desitjos de Lluís XIV, es realitzen canvis profunds a l'interior de la catedral. L'arquitecte Robert de Cotte va demolir el cor alt (que va ser reemplaçat per una sumptuosa reixa daurada de ferro forjat), part de l'alt relleu del tancament del cor a fi d'obrir-lo al deambulatori substituint-los per reixes, i també les tombes per permetre una remodelació completa del cor a l'estil de l'època, igual que moltes altres catedrals gòtiques de tot Europa durant els segles xvii i xviii. Es van fer noves cadires per al cor així com un nou altar per al qual es varen fer les estàtues que encara avui l'adornen, representant Lluís XIV renovant el vot del seu pare, Lluís XIII, tots dos de genollons al davant de la Pietat. Després, el 1756, els canonges varen trobar l'edifici massa fosc i demanaren als germans Le Vieil que llevassin els vitralls medievals i els reemplacessin per vidre blanc, després van fer enlluir les parets de la catedral. Els rosetons s'han conservat. Finalment, a petició del clergat, Soufflot, arquitecte del Panteó de París, va fer desaparèixer l'entrepany (part d'una paret compresa entre dues portes o forats) i una part del timpà del portal central, decorada amb el famós Judici Final, per deixar passar més fàcilment el pal·li de les processons.

Durant la revolució francesa, la catedral va ser objecte de nombrosos actes vandàlics, per exemple, els revolucionaris van confondre els reis de Judà de la Galeria dels Reis de la façana amb reis francesos i els van arrencar els caps. L'any 1977 es varen trobar una bona part d'aquests caps i ara són al Museu Nacional de l'Edat Mitjana. Entre altres actes vandàlics, quasi totes les grans estàtues dels portals van ser destruïdes i el tresor va ser saquejat. Els altars es varen destruir completament, i el mobiliari de culte, estàtues, pintures, adorns, domassos, també varen ser destruïts o dispersats. El culte a la Raó es va iniciar a Notre-Dame el 10 de novembre del 1793, amb el Festival de la Llibertat. Aquest culte va ser organitzat per Pierre-Gaspard Chaumette, i l'altar es va veure transformat en l'altar de la deessa Raó. A la fi de novembre d'aquell any, el culte catòlic va ser prohibit a París. La catedral es va transformar en magatzem.

La restauració del segle xix  Notre Dame a final del segle xix La catedral el 1840. Aquest daguerreotip mostra l'edifici en un estat de ruïna avançada abans del programa de restauració de Viollet-le-Duc. Notau l'absència d'estàtues en la galeria dels reis (destruïdes per la Revolució) i el portal del Judici Final radicalment transformat par Soufflot.

Poc després de la signatura del Concordat de 1801, la catedral va ser retornada al culte (18 d'abril del 1802). Es va procedir ràpidament a algunes reparacions d'emergència perquè al desembre del 1804, Napoleó Bonaparte pogués ser coronat emperador dels francesos, en presència del papa Pius VII. L'edifici va ser blanquejat per a l'ocasió, i després amagat sota les decoracions de Charles Percier i Fontaine François-Léonard. Les banderes d'Austerlitz es varen penjar a les parets per amagar el lamentable estat de l'edifici.

Una vegada que es restableix la pau, la catedral estava en tan mal estat que les autoritats municipals van començar a considerar la possibilitat d'enderrocar-la totalment. El gran novel·lista Victor Hugo, admirador de la construcció, va escriure aleshores la seva novel·la Notre-Dame de París (publicada el 1831), que va ser un gran succés i va ser escrita especialment per sensibilitzar la gent sobre el valor d'aquest monument. Va aconseguir crear un ample moviment popular a favor de la catedral. La novel·la va retornar a la vida un monument aleshores marginat i el va fer més familiar als parisencs. A això es va afegir el pes del nou moviment europeu anomenat romanticisme que cercava donar als homes una nova concepció del món. Amb a aquesta novel·la, Víctor Hugo va contribuir de forma especial en salvar l'obra mestra d'un destí fatal.

Va haver diferents corrents de pensament sobre el destí que havia de tenir Notre Dame: els catòlics, per descomptat que volien reconciliar França amb la pietat i la fe d'abans, els monàrquics que van tractar de reviure el passat proper, i també hi havia un corrent laic.

El ministre d'Afers Religiosos de l'època va decidir un gran programa de restauració. L'arquitecte Godde encarregat fins aleshores del manteniment de l'edifici i els mètodes de restauració del qual van ser unànimement rebutjats, va ser descartat. Es consideren Jean-Baptiste-Antoine Lassus i Eugène Viollet-le-Duc que s'havien distingit en les obres de la Santa Capella de París. Aquests últims van dipositar un projecte i un informe i varen guanyar el concurs que es va realitzar el 1844; varen presentar el 1845 un pressupost de 3.888.500 francs que varen haver de reduir a 2,65 milions, per a la renovació de la catedral i construcció d'una sagristia. L'Assemblea Nacional va aprovar una llei que concedia aquesta quantitat i és així com, després de llargs anys d'espera, la restauració podria realment començar. L'exigu pressupost es va esgotar el 1850. Els treballs es varen aturar. Viollet-le-Duc, va haver de presentar noves propostes en repetides ocasions perquè els treballs es poguessin acabar. En total es varen concedir més de dotze milions de francs. Havent mort Lassus el 1857, ell va ser l'únic que va acabar la restauració el 31 de maig 1864.

La construcció de la sagristia va resultar ser un desastre financer. Va fer falta baixar fins a 9 metres abans de trobar-se amb un terreny estable.

El lamentable estat de la part que correspon a l'obra era generalitzat, per exemple, la porta vermella era en ruïna. S'ha perdut el compte dels pinacles trencats, els gablets ensorrats. Pel que fa a les grans escultures dels portals i de la façana, no quedava gran cosa. Els restauradors van haver de fer un seriós treball d'investigació per poder restaurar (de forma idèntica si fos possible, que era rar en aquella època) les parts deteriorades, com es reflecteix en els escrits i dibuixos de Viollet-le-Duc.

Va ser la restitució de la part escultòrica de la catedral el que va constituir el principal èxit dels dos arquitectes. D'entrada varen voler restaurar tota l'ornamentació escultòrica destruïda, inspirant-se o copiant obres de la mateixa època i que es conservaven intactes (Amiens, Chartres i Reims). Per això els arquitectes varen reunir un excel·lent equip d'escultors dirigits per Adolphe-Victor Geoffroy-Dechaume. Molts d'ells procedien del taller de David d'Angers, i es coneixien entre si. Més de cent grosses estàtues van ser creades i destinades a l'exterior, entre elles les dotze estàtues de coure al voltant de la base de l'agulla, obres del mateix Geoffroy-Dechaume, cosa que demostra el gran talent d'aquest escultor. Viollet-le-Duc va prestar molta atenció a la realització d'aquestes estàtues. Primer eren dissenyades amb molta cura, després es realitzava una maqueta en guix de grandària natural i a continuació es feien les correccions necessàries fins que l'obra es considerava satisfactòria. Només llavors, es feia l'estàtua definitiva en pedra. Les escultures varen ser controlades totalment pels arquitectes i no es va autoritzar cap mena de llibertat de creació als escultors.

Durant la restauració, la catedral va ser remodelada una mica. El rosetó sud per exemple, es va girar quinze graus a fi de fer-lo reposar segons un eix vertical. Aquesta modificació, encara que criticada, era deguda a la necessitat de consolidar el conjunt, ja que l'obra s'havia enfonsat una mica. Finalment algunes estàtues sorgides de la imaginació de l'arquitecte es varen construir, com les impressionants gàrgoles en forma de quimeres contemplant París des de dalt de la façana.

A més de tot això es va planificar un aïllament de la catedral arrasant amb tots els edificis dels voltants.

La restauració es va completar quan Georges Darboy era arquebisbe de París, el qual va consagrar la catedral el 31 maig del 1864.

De la restauració del segle xix fins a l'actualitat  Notre-Dame de París (hi ha agulla) el 1930 ca.

Poc després, la Comuna de París de 1871 va estar a punt de destruir l'edifici. Els manifestants van calar foc a alguns bancs i cadires, però el foc va ser ràpidament extingit i va causar danys molt escassos. La catedral va passar les dues guerres mundials sense tenir problemes significatius.

En la dècada del 1990, els mètodes moderns varen ajudar a retornar a la pedra exterior de la catedral, ennegrida per segles, la seva puresa i blancor original. Es distingeixen dues capes diferents de contaminació que ennegrien la pedra: una part marró corresponent a la part de la pedra exposada a l'aire i la llum solar i una capa negra en la superfície formada per guix (sulfat de calci hidratat).

La pol·lució atmosfèrica suposà un perill per al manteniment de l'estructura de la catedral, tal com informà un article del New York Times el 1991.[1]

Un article de Time del 2017 informava que l'edifici requeria de reparacions especialment per l'oratge i la pol·lució atmosfèrica. La reparació requeria molts diners, amb una responsabilitat dividida entre l'arxidiòcesi i l'estat francès. El Ministeri de Cultura donava anualment dos milions d'euros per a reparacions, però no era prou.[2] La ineficiència burocràtica va comportar dècades de negligència per al correcte manteniment de l'edifici.[3]

El 2018, una organització benèfica va reunir fons a Boston per tractar de finançar la correcta reparació de la catedral.[4]

La brutícia, que representava un perill per a la pedra, va ser eliminada. Les escultures van ser tractades amb làser, micro-engomat i compreses humides per eliminar la pols sense alterar la pàtina. Les pedres més deteriorades s'han substituït per altres idèntiques, extretes de jaciments de la regió parisenca. A més, una xarxa del fils d'electricitat, invisible des del terra, ha provocar la sortida dels coloms dels quals els excrements àcids van deteriorar moltes pedres.[5]

 Notre-Dame durant l'incendi el 2019.

El 15 d'abril de 2019, un incendi important va destruir parts de la catedral. L'agulla va caure,[6] i el sostre es va esfondrar.[7] L'incendi pot estar relacionat amb les restauracions en curs i causat per una de les tarimes instal·lades, segons la hipòtesi principal.[8]