Prvá katedrála Paríža vznikla v druhej polovici 6. storočia západne od dnešnej budovy. Výstavba dnešnej katedrály trvala od roku 1163 do roku 1345 a začal ju Ľudovít VII. V tom čase bol Paríž len biskupstvom.

V 19. storočí ju reštaurovali pod vedením Viollet-le-Duca. O výstavbe Notre Dame rozhodol parížsky biskup Maurice de Sully v roku 1159, základný kameň katedrály položili v roku 1163 a jej výstavba trvala 182 rokov, celkovo ju dostavali v roku 1345. Neskôr prešla rozsiahlou rekonštrukciou.

Ide o ranogotickú stavbu, ktorá sa stala základom a inšpiráciou pre ďalšie významné gotické stavby, predovšetkým sakrálne stavby nielen vo Francúzsku, ale aj v celej Európe. Je jedinečná nielen svojím vzhľadom, ale aj celkovou konštrukciou a architektúrou. Tvorí ju 5 lodí – jedna hlavná a štyri bočné. Súčasťou západnej fasády sú tri hlavné vchody, nad prostredným dominuje vitrážové okno rozetového tvaru. Nad hlavnými vchodmi sa týčia dve predné hlavné veže – zvonice.

Katedrála Notre Dame je zaradená medzi svetové kultúrne dedičstvo UNESCO.

V roku 1804 sa tu odohralo pomazanie Napoleona I. pápežom.

Katedrála stojí na mieste, ktoré už takmer 2000 rokov slúži náboženským kultom. V 4. storočí na jej mieste stál galsko-rímsky chrám zasvätený Jupiterovi, neskôr v 6. storočí už kresťanská bazilika.

Počas Veľkej francúzskej revolúcie v roku 1793 katedrálu zničili a vyrabovali revolucionári, ktorí tiež roztopili drahé kovy na oltároch. Rozbili všetkých 28 sôch biblických kráľov na priečelí budovy, pretože ich považovali za francúzskych kráľov. Po revolúcii hrozilo, že stavbu so zbúranými stenami a vytlčenými oknami zbúrajú. Do osudu katedrály však šikovne zasiahol spisovateľ, Parížan Victor Hugo a jeho román Chrám Matky Božej v Paríži publikovaný v roku 1831. Toto dielo vyvolalo taký veľký záujem o osud chrámu, že vďaka nemu sa podarilo získať peniaze na jej obnovu formou verejnej zbierky.