On pense qu’au début de l’ère chrétienne il existait à l’emplacement de Notre-Dame, un temple païen, remplacé ultérieurement par une grande basilique chrétienne sans doute assez semblable aux basiliques antiques. Nous ne savons pas si cet édifice, dédié à saint Étienne, a été élevé au IVe siècle et remanié par la suite ou si il date du VIe siècle avec des éléments plus anciens réemployés (hypothèse de la cathédrale de Childebert Ier, fils de Clovis et de Clotilde).
Quoi qu’il en soit, cette cathédrale Saint-Étienne était de très grandes dimensions pour l’époque. Sa façade occidentale, se trouvait à une quarantaine de mètres plus à l’ouest que la façade actuelle de Notre-Dame et avait une largeur à peine inférieure : elle mesurait 36 mètres. Quant à la longueur de l’ancien édifice, elle était de 70 mètres, c’est-à-dire un peu plus de la moitié de la longueur de la cathédrale actuelle. Des rangées de colonnes de marbre séparaient cinq nefs. L’édifice était orné de mosaïques. Elle était complétée sur son flanc nord par un baptistère, appelé Saint-Jean le Rond. La présence d’un baptistère est attestée avant 451.
La cathédrale Saint-Étienne semble avoir été régulièrement entretenue et réparée, suffisamment en tout cas pour résister aux guerres et aux siècles. Cependant, en 1160, l’évêque Maurice de Sully décida la construction d’un sanctuaire d’un nouveau type beaucoup plus vaste. Comme dans l’ensemble de l’Europe de l’Ouest, les XIIe et XIIIe siècles se caractérisent en effet par une rapide augmentation de la population des villes françaises, liée à un important développement économique, et les anciennes cathédrales étaient un peu partout devenues trop petites pour contenir les masses de plus en plus grandes de fidèles. Les spécialistes estiment que la population parisienne passe en quelques années de 25 000 habitants en 1180, début du règne de Philippe II Auguste, à 50 000 vers 1220, ce qui en fait la plus grande ville d’Europe, en dehors de l’Italie.
L’architecture de la nouvelle cathédrale devait s’inscrire dans la ligne du nouvel art que l’on appellera gothique ou ogival. Plusieurs grandes églises gothiques avaient déjà été inaugurées à ce moment : l’Abbatiale Saint-Denis, la cathédrale de Noyon et celle de Laon, tandis que celle de Sens était en voie d’achèvement. La construction, commencée sous le règne de Louis VII dura de 1163 à 1345. À cette époque, Paris n’était qu’un évêché, suffragant de l’archevêque de Sens.
En 1163 a lieu la pose de la première pierre par le pape Alexandre III alors réfugié à Sens, en présence du roi Louis VII. L’essentiel des travaux se fera sous la direction de l’évêque Maurice de Sully (1160-1197) et de son successeur Odon de Sully (1197-1208), ce dernier sans lien de parenté avec le premier. On distingue quatre campagnes d’édification correspondant à quatre maîtres d’œuvre différents dont les noms ne nous sont pas parvenus.
À cette époque, on s’aperçut que les portails du transept, construits en style roman, contrastaient par la sévérité de leur style avec la grande façade gothique richement ornée au goût du jour. La reconstruction des parties romanes fut alors prestement décidée par l’évêque Renaud de Corbeil (1250-1268).
Nous connaissons les noms des maîtres d’œuvre qui se sont succédé durant cette période. Il s’agit de Jean de Chelles, Pierre de Montereau, Pierre de Chelles, Jean Ravy, Jean le Bouteiller et Raymond du Temple.
Jean de Chelles procéda à l’allongement du transept, au nord d’abord (vers 1250), puis au sud. On lui doit la façade nord du transept et sa superbe rosace. Suite à son décès en 1265, son travail sur le croisillon sud fut terminé par Pierre de Montreuil à qui l’on doit la façade sud du transept et sa tout aussi belle rosace. Il mourut en 1267. Pierre de Montreuil avait également achevé les chapelles et la porte rouge. De même, il débuta le remplacement des arcs-boutants du chœur.
Son successeur Pierre de Chelles construisit le jubé et commença les chapelles du chevet en 1296.
Ces dernières furent achevées par Jean Ravy qui fut maître d’œuvre de 1318 à 1344. Jean Ravy débuta la construction des admirables arcs-boutants du chœur d’une portée de 15 mètres. Il commença aussi la confection de la clôture du chœur.
En 1344, son neveu Jean le Bouteiller lui succéda jusqu’en 1363.
Après son décès, son adjoint Raymond du Temple termina les travaux, et notamment la superbe clôture du chœur.
Pendant près de trois siècles, on respecta la structure gothique de la grande cathédrale, mais les choses changèrent dès la fin du XVIIe siècle, sous le règne de Louis XIV.
La société de cette époque (fin du XVIIe - XVIIIe siècle) n’aimait pas le gothique, jugé art barbare, sombre, archaïque et bien trop austère. Plus d’un prélat rêvait de démolir sa cathédrale gothique pour la remplacer par un sanctuaire classique. L’obstacle principal était le coût des travaux : détruire et reconstruire une cathédrale coûtait extrêmement cher, et la baisse de la piété, constante depuis la Renaissance, n’était guère propice à la collecte de fonds en faveur d’une gigantesque église. De plus la noblesse — dont les rois —, jadis grande pourvoyeuse de fonds, était bien trop occupée à se construire de somptueux châteaux et à y mener grand train de vie ; quant au petit peuple des fidèles, il n’avait pas les moyens. On se bornait donc à cette époque à reconstruire, généralement en style classique, ce qui s’était effondré (comme la façade de la cathédrale de Luçon ou encore l'intégralité de celle de Rennes), ou alors à détruire et remplacer ce que l’on pouvait détruire et remplacer à moindre frais, à savoir les œuvres d’art et la décoration intérieure.
Ainsi dès la fin du XVIIe siècle, Robert de Cotte démolit le jubé, les stalles, les bas-reliefs des clôtures, ainsi que des tombeaux, cela pour la réalisation du vœu de Louis XIII fait en 1638. Puis en 1756, les chanoines jugeant l’édifice trop sombre demandèrent aux frères Le Vieil de détruire les superbes vitraux du Moyen Âge et de les remplacer par du verre blanc ; après quoi on badigeonna les murs de la cathédrale… Les rosaces furent épargnées. Notre-Dame de Paris fut beaucoup plus touchée par ces changements que les cathédrales des provinces pauvres, dont le clergé n’avait pas les moyens de se payer le saccage de leurs propres églises. Enfin, à la demande du clergé, Soufflot, architecte du Panthéon de Paris, fit disparaître le linteau et une partie du tympan du portail central, y compris une partie du célèbre Jugement Dernier, pour laisser passer plus aisément le dais des processions.
Au cours de la Révolution française, de nombreux actes de vandalisme visèrent la cathédrale : les rois de Juda de la Galerie des Rois de la façade furent décapités et enlevés — on croyait qu’il s’agissait des rois de France. On a retrouvé une bonne partie de ces têtes en 1977, et elles se trouvent actuellement au Musée national du Moyen Âge. Entre autres déprédations, presque toutes les grandes statues des portails furent anéanties et le trésor fut pillé. Le Culte de la Raison fit son apparition à Notre-Dame de Paris le 10 novembre 1793, avec la Fête de la Liberté. Ce culte fut organisé par Pierre-Gaspard Chaumette, et le maître-autel se vit ainsi transformé en autel de la déesse Raison. Fin novembre de cette année, le culte catholique fut d’ailleurs interdit à Paris. La cathédrale fut ensuite transformée en entrepôt.
Peu après la signature du concordat de 1801, la cathédrale fut rendue au culte (18 avril 1802). On procéda rapidement à quelques réfections d’urgence si bien qu'en décembre 1804, Napoléon Bonaparte put s’y sacrer empereur des Français, en présence du pape Pie VII. L’édifice avait été blanchi à la chaux pour la circonstance, puis dissimulé sous des décors de Charles Percier et François-Léonard Fontaine. Les drapeaux d’Austerlitz avaient été accrochés aux murs afin de masquer le pitoyable état de l’édifice.
Une fois la paix retrouvée, la cathédrale était dans un tel état de délabrement que les responsables de la ville commencèrent à envisager la possibilité de l’abattre totalement. Le grand romancier Victor Hugo, admirateur de l’édifice, écrivit alors (1831) son roman Notre-Dame de Paris qui eut un énorme succès et avait notamment pour but de rendre le public conscient de la valeur d’un tel monument. Il réussit à créer un large mouvement populaire d’intérêt en faveur de la cathédrale. Son roman avait rendu vie à un monument alors marginalisé et l’avait rendu plus familier aux parisiens. À cela s’ajoutait le poids du nouveau courant européen appelé romantisme qui s’efforçait de donner aux hommes une nouvelle conception du monde. Par son roman, Victor Hugo contribua largement à sauver le chef-d’œuvre meurtri d’un destin fatal.
Le sort de Notre-Dame focalisa différents courants de pensée : les catholiques bien sûr qui désiraient réconcilier la France avec la piété et la foi d’antan, les monarchistes aussi qui s’efforçaient de renouer avec un proche passé, mais aussi le courant laïc épris de générosité.
Le Ministre des Cultes de l’époque décida d’un grand programme de restauration. L’architecte Godde chargé jusqu’alors de l’entretien de l’édifice et dont les méthodes de restauration faisaient l’unanimité contre elles fut écarté. On se tourna vers Jean-Baptiste-Antoine Lassus et Eugène Viollet-le-Duc qui s’étaient distingués sur le chantier de la Sainte-Chapelle. Ces derniers déposèrent un projet et un rapport, et ayant emporté l’appel d'offres en 1844, présentèrent en 1845 un budget de 3 888 500 francs, qu’ils durent réduire à 2 650 000, pour la réfection de la cathédrale et la construction d’une sacristie. L’Assemblée Nationale vota une loi accordant cette somme et c’est ainsi qu’après de longues années d’attente, la restauration put vraiment débuter. Le maigre budget fut épuisé en 1850. Les travaux s’arrêtèrent. Viollet-le-Duc dut présenter à plusieurs reprises de nouvelles propositions afin que les travaux puissent se terminer. Au total plus de douze millions de francs furent ainsi octroyés. Lassus étant décédé en 1857, c’est lui seul qui termina la restauration le 31 mai 1864.
La construction de la sacristie se révéla un gouffre financier. Il fallut en effet descendre à neuf mètres avant de rencontrer un terrain stable.
L’état lamentable des maçonneries de la cathédrale était généralisé, la porte rouge par exemple était en ruines. On ne comptait plus les pinacles brisés, les gables effondrés. Quant à la grande statuaire des portails et de la façade, il n’en restait plus grand chose. Les restaurateurs durent effectuer un profond travail de recherche afin de restituer (à l’identique si possible, ce qui l’était rarement) les parties dégradées, ce dont témoignent les écrits et dessins de Viollet-le-Duc.
C’est la restitution du programme sculpté de la cathédrale qui constitue la principale réussite des deux architectes. Ils ont d’emblée voulu reconstituer toute l’ornementation sculpturale détruite en s’inspirant ou copiant des œuvres de la même époque et restées intactes (Amiens, Chartres et Reims). Pour ce faire les architectes réunirent une équipe d’excellents sculpteurs sous la direction d’Adolphe-Victor Geoffroy-Dechaume. Beaucoup d’entre eux provenaient de l’atelier de David d’Angers et se connaissaient. Plus de 100 grandes statues furent ainsi créées à destination de l’extérieur, dont les douze statues en cuivre entourant la base de la flèche, œuvres de Geoffroi-Dechaume lui-même, qui témoignent du grand talent de ce sculpteur. Viollet-le-Duc apporta un très grand soin à la réalisation de ces statues. Elles étaient d’abord dessinées par ses soins, puis une maquette grandeur nature en plâtre était réalisée. On apportait alors les corrections nécessaires jusqu’à ce que l’œuvre soit jugée satisfaisante. À ce moment seulement, on procédait à la réalisation de la statue définitive en pierre. Aucune liberté de création n’était autorisée de la part des sculpteurs dont le travail était totalement contrôlé par les architectes.
Lors de la restauration, la cathédrale fut quelque peu remaniée. La rosace sud par exemple fut pivotée de quinze degrés afin de la faire reposer selon un axe vertical, modification qui, parfois critiquée, était motivée par la nécessité de consolider l’ensemble dont la maçonnerie s’était affaissée. Enfin quelques statues sorties de l’imagination de l’architecte furent édifiées, telles les impressionnantes chimères contemplant Paris du haut de la façade.
La restauration achevée, c’est monseigneur Darboy, archevêque de Paris, qui consacra la cathédrale le 31 mai 1864.
Peu de temps après, la Commune de 1871 faillit anéantir l’édifice. Des émeutiers mirent le feu à quelques bancs et chaises, mais l’incendie fut vite maîtrisé et ne causa que des dégâts très légers.
La cathédrale passa les deux guerres mondiales sans problèmes notables.
Dans les années 1990, les procédés modernes ont permis de redonner à la pierre extérieure de la cathédrale noircie par les siècles, sa pureté et sa blancheur d’origine. On distinguait deux couches distinctes de pollution qui noircissait la pierre :
La crasse, représentant un danger pour la pierre, a été éliminée. Les sculptures ont été traitées par laser, micro-gommage et compresses humides afin de pulvériser la poussière sans altérer la patine du temps. Les pierres trop détériorées ont été remplacées par d’autres, identiques, prélevées en région parisienne dans des gisements de calcaire coquillier. De plus, un réseau de fils électriques, invisibles depuis le sol, a entraîné le départ des pigeons responsables d’altérations importantes au niveau des pierres.
Notre-Dame bien avant son achèvement est le lieu de moult événements religieux et politiques de l’histoire de France :