De bouwheer was Mauritius van Sully, bisschop van Parijs. Hij had de steun van koning Lodewijk VII van Frankrijk en van het kapittel. Bisschop De Sully liet eerst de Sint-Stefanuskathedraal, gelegen vlak voor de latere Notre-Dame, tot de grond afbreken. De kathedraal was ontstaan in de 4e eeuw en in haar grootse dimensies uitgebouwd in de 6e[1][2] of 7e[3][4] eeuw, naargelang de bronnen. De eerste steen van de Notre-Dame werd in het voorjaar van 1163 (volgens het Memoriale Historiarum van kroniekschrijver Jean de Saint-Victor tussen 24 maart en 25 april) door paus Alexander III en Lodewijk VII van Frankrijk geplaatst.

Tegen 1177 was het koor voltooid en op 19 mei 1182 werd het nieuwe hoogaltaar ingewijd door kardinaal Henri de Château-Marçay, de pauselijke gezant in Parijs, en Maurice de Sully. Men bouwde destijds doorgaans eerst het koor, zodat de kerk al gebruikt kon worden terwijl er elders nog gebouwd moesten worden. Na de dood van bisschop Maurice de Sully in 1196, werd onder zijn opvolger Eudes de Sully begonnen met de bouw van het transept en het schip. Halverwege de 13e eeuw waren ook de westtorens voltooid, waarna tot 1345 nog gewerkt werd aan het interieur en de straalkapellen.

In 1793, tijdens de Franse Revolutie, werd de kathedraal omgedoopt tot Tempel van de Rede. In deze periode werden talloze kunstwerken gestolen of vernield. De 28 beelden van de koningen van Juda op de westgevel werden onthoofd omdat men dacht dat het beelden van Franse koningen waren. Na de ondertekening van het Concordaat van 15 juli 1801 werd de Notre-Dame opnieuw gebruikt voor de Heilige Mis. Drie jaar later was de Notre-Dame de plek waar de kroning van Napoleon Bonaparte plaatsvond. De kerk werd op 27 februari 1805 als eerste in Frankrijk door paus Pius VII verheven tot basilica minor.

De kathedraal onderging vanaf 1845 een 23 jaar durende restauratie door Eugène Viollet-le-Duc, om de beschadigingen van de Franse Revolutie te herstellen. Viollet-le-Duc verving de deels vernielde koningsbeelden in het voorfront door zelfontworpen beelden. Hij plaatste ook een nieuwe vieringtoren of flèche op het dak van de kathedraal. Sinds 1991 is er een nieuw restauratieproject.

  Zie Brand in de Notre-Dame van Parijs voor het hoofdartikel over dit onderwerp.

Op 15 april 2019 brak er in de avond tijdens restauratiewerkzaamheden een hevige brand uit, die zich vanuit het middenschip snel verspreidde.[5] Het dak en de centrale torenspits (vieringtoren) stortten in. De rest van het gebouw, alsook een aantal belangrijke kunstschatten, konden nog worden gered.