On date de la seconde moitié du IVe siècle l’implantation d’une première cathédrale dans l’île de la Cité. Selon les données archéologiques et historiques dont on dispose, cette première basilique paléochrétienne était accolée à un baptistère.
L’église Saint-Etienne, également édifié sur l’île de la Cité, est mentionnée dans un texte du VIIe siècle. Qualifiée de basilique, Saint-Etienne ne devait être qu’un un sanctuaire satellite de la cathédrale.
Edifié à l’emplacement de la première cathédrale paléochrétienne, un édifice à cinq nefs et doté d’un avant-corps occidental date probablement de la période carolingienne, dans la première moitié du IXe siècle.
Une cathédrale romane
Un précepte du roi Louis VI de 1122 mentionne une ancienne ecclesia mais également une nouvelle ecclesia (terme qui ne peut désigner qu’une cathédrale). La vieille cathédrale doit se rapporter à celle édifiée à l’époque carolingienne, alors que la nouvelle a sans doute été édifiée plus à l’est, à l’emplacement de l’actuelle cathédrale gothique, et date vraisemblablement de la fin du XIe siècle et du début du XIIe siècle.
Sur le frontispice de cette cathédrale romane ont été aménagés deux portails à statues- colonnes illustrant le premier art gothique, peut-être même trois si l’on se réfère aux modèles à trois portails sculptés des façades contemporaines de Chartres et de Saint-Denis.
Le portail Sainte-Anne, remployé pour la cathédrale gothique, a été gravement mutilé durant la Révolution et ensuite restauré par Viollet-le-Duc et son sculpteur Geoffroy-Dechaume.