La première des devancières de l’actuelle église Notre-Dame fut érigée, admet-on, à partir de 752 par Boniface, sans que l’on sache à quel endroit et sous quelle forme. Lors d’investigations archéologiques menées en 1991 à l’occasion de l’installation d’un orgue sur la paroi occidentale de la nef, l’on découvrit à 3 m de profondeur une abside occidentale, en maçonnerie simple, dont on crut tout d’abord, à tort, qu’elle datait du IXe siècle, mais qu’un réexamen ultérieur situa à une époque plus récente, sans doute le XIIe siècle.
La première attestation écrite de l’église Notre-Dame date de 1117. Un document de 1153 rapporte l’écroulement de l’église principale d’Erfurt, la « major ecclesia », et en 1154 fut commencée la construction sur le Domberg d’une basilique de style roman tardif. Cependant, il faut se garder de prendre pour certain que l’église de Boniface se soit maintenue jusqu’en 1153, et que l’édifice se soit effectivement effondré. Il est beaucoup plus vraisemblable que les chanoines et l’archevêque de Mayence désiraient entreprendre la construction d’une nouvelle église pour ne pas être en reste par rapport à l’église Saint-Sévère voisine et au couvent Saint-Pierre, reconstruits après avoir été détruits par un incendie en 1142. Il n’est pas exclu cependant que l’incendie se soit propagé jusqu’à l’église Notre-Dame.
La construction progressa rapidement, aidée par le fait que l’on mit au jour en 1154, lors des travaux, deux sépultures contenant ce qui allait être identifié comme étant les restes des saints évêques Adolar et Eoban, ce qui, par le biais des dons et des offrandes auxquels cette découverte donna lieu par la suite, contribua grandement au financement du projet. Dès 1170, l’église était utilisable, à telle enseigne que cette même année, Louis III de Thuringe, fils du landgrave Louis II de Thuringe (dit Louis de Fer), fut adoubé ici par l’empereur Frédéric Ier Barberousse.
Les deux objets mobiliers les plus anciens de la cathédrale remontent également à cette époque : la statue qu’il est convenu d’appeler le Wolfram, et une madone romane en stuc, datant tous deux de 1160 environ. En ce qui concerne le Wolfram, il s’agit d’un grand chandelier en bronze, de la taille d’un être humain, figurant un homme dont les bras correspondent aux branches du chandelier, fabriqué vraisemblablement dans la fonderie de Magdebourg; c’est probablement une des sculptures en bronze et autonomes les plus anciennes de toute l’Allemagne. Le donateur Wolfram, dont le nom, en même temps que celui de son épouse Hiltiburc, est mentionné dans une inscription ciselée sur un des cordons pendants de la ceinture, est très probablement identique à Wolframus scultetus, membre de la petite noblesse de Mayence, et dont le nom apparaît deux fois en 1157 dans des chartes.
À la date du 20 juin 1182 nous est rapportée une consécration de l’église, consécration qui pourrait bien avoir concerné l’ensemble de l’édifice, sans toutefois que les travaux de construction fussent nécessairement à ce moment tous achevés; en effet, d’autres textes font part de l’achèvement des clochers, suivie d’une nouvelle consécration, le 5 octobre 1253, événement dans lequel on a été tenté, dans la littérature plus ancienne en particulier, de voir le point d’achèvement de l’édifice roman. Cependant, il ne put alors s’agir que d’une reconsécration consécutive à des travaux de transformation ou d’extension, probablement au voûtement du sanctuaire, lequel avait, au moins jusqu’à 1238, un plafond plat.
De cet édifice roman de la seconde moitié du XIIe siècle, basilique à plan en forme de croix, se sont conservées : la partie inférieure des clochers, parties comportant chacune deux étages quadrangulaires, les portions occidentales du déambulatoire du chœur, et quelques parties du transept. Les étages des tours situés au-dessus des deux étages inférieurs, et qui adoptent un plan octogonal, datent de la fin du XIIe siècle et de la première moitié du XIIIe. Le clocher sud fut achevé en 1201 et le clocher nord en 1237, cependant tous deux furent ultérieurement remaniés et même reconstruits au XVe siècle.
Comme pour d’autres cathédrales et collégiales, le besoin se fit sentir à l’époque gothique de remanier l’édifice, en particulier le chœur, de façon à l’agrandir et de le rendre plus lumineux, d’autant que l’espace ne suffisait plus pour accueillir tous les chanoines, leur nombre ayant, suite à la fondation de plusieurs couvents, considérablement augmenté ― en effet, plus de 100 membres du clergé, voire, les jours de fête, jusqu’à 300 de ces personnes, participaient aux célébrations.
C’est pourquoi, dès les années 1280, l’on commença d’adjoindre un nouveau chœur, plus vaste, se terminant par une abside polygonale. En 1290 eut lieu la consécration de la première extension du chœur. Dans la foulée, l’on entreprit d’ériger la tour médiane, laquelle fut achevée dès avant 1307. Elle sert de clocher, hébergeant entre autres la célèbre cloche Gloriosa, consacrée pour la première fois en 1251, et refondue à plusieurs reprises depuis, la dernière fois en 1497.
Toutefois, l’espace offert par l’édifice venant derechef à être insuffisant, l’on créa au XIVe siècle un nouveau chœur, une fois encore sensiblement agrandi, tandis que dans le même temps des travaux de grande ampleur furent entamés dans le reste du bâtiment. Le haut chœur, dont la construction fut reprise en 1349 (à ce moment, les premiers mètres inférieurs de la maçonnerie s’y dressaient déjà, achevés, depuis une génération), et qui fut clos par une abside semi-circulaire, fut consacré par l’évêque auxiliaire de Constance, Friedrich Rudolf von Stollberg, qui occupa cette fonction entre 1370 et 1372.
En ce qui concerne le chœur, il y a lieu pour l’heure (avant d’y revenir plus en détail ci-dessous) de relever en particulier le cycle de vitraux gothiques (environ 1370–1420), un des mieux préservés d’Allemagne, et l’ameublement, également largement originel. Les stalles, réalisées en 1329, comptent parmi les stalles médiévales les plus vastes d’Allemagne et sont d’une meilleure facture que dans mainte autre cathédrale. La datation [[Dendrochronologie |dendrochronologique]] des stalles a montré que les projets de construction de l’église ont de beaucoup précédé leur réalisation : en 1329 n’avaient encore été élevés que les premiers mètres inférieurs des murs du haut choeur, et ce n’est qu’à partir de 1349, après une interruption, que fut reprise la construction.
Le chœur est posé sur une sorte d’énorme soubassement, appelé Kavaten en allemand (cavées, du latin cavare, creuser), que, jusqu’en 1329, l’on travailla à aménager là afin d’agrandir artificiellement, en direction de l’est, le Domhügel, c’est-à-dire la butte (Hügel) sur laquelle se dresse la cathédrale (Dom). Au Moyen Âge, et encore ultérieurement, des maisons furent construites au-dedans de ce soubassement, mais furent supprimées au XIXe siècle. L’aménagement des Kavaten permit parallèlement la construction d’une église basse (allem. Unterkirche) ― la dénomination de crypte est, en l’espèce, inappropriée ―, qui fut consacrée en 1353. Cette église basse gothique, en plus d’être lieu de prière, était en même temps chemin de procession, assurant le parcours de la procession du Saint-Sang, qui, longeant le chœur, peut emprunter deux portes opposées de l’église basse, ce qui rend superflu un accès direct à partir de l’église haute superposée.
Des interventions et ajouts de l’époque moderne contribuent également à déterminer l’aspect actuel du chœur, comme l’attique et les pinacles couronnant la muraille, les statues de saints devant les contreforts et d’autres éléments décoratifs. En revanche, la chaire extérieure fixée à un des piliers du soubassement remonte bien au Moyen Âge.
Concomitamment avec la construction des Kavaten aux alentours de 1330, fut réalisée l’entrée principale de l’édifice, savoir la structure accotée au bras nord du transept, laquelle, s’avançant en hors-œuvre, fait porche et présente un portail à gâble. Un telle disposition est inhabituelle, car la façade représentative, avec portail, de la cathédrale ne se situe pas sur sa face occidentale, mais s’aperçoit lorsque l’on vient du nord-ouest. Cette disposition a été commandée principalement par l’espace limité qu’offre le Domhügel, qu’il fallait partager avec l’église Saint-Sévère voisine et avec l’importante cité médiévale à l’est de la cathédrale. Les sculptures qui ornent cette entrée figurent les douze apôtres et la parabole des dix vierges, dont Ecclésia et Synagogue.
En 1452 l’avis fut diffusé que la nef menaçait de s’écrouler. Certes, une telle affirmation n’était pas tout à fait invraisemblable, attendu qu’on utilisait encore alors l’antique nef romane, mais on est tenté de croire que c’est plutôt le vœu d’une construction neuve, capable de soutenir la comparaison avec l’église St.-Sévère voisine, qui fit qu’on résolut de bâtir une nouvelle nef. L’église St.-Sévère s’était déjà dotée d’une nouvelle nef dès le milieu du XIVe siècle, à la suite d’un incendie.
En 1455, la nef romane fut définitivement démolie et la construction d’une église-halle de style gothique tardif fut commencé. La volonté des membres du chapitre de créer davantage de place pour la communauté des fidèles constitua le motif apparent de ce remaniement. La part propre que la population civile prit dans le financement du projet a semble-t-il été importante. La date précise à laquelle la nef fut achevée n’est pas parvenue jusqu’à nous ; cependant l’église était de nouveau utilisable aux environs de 1465, vu qu’il était question à cette date d’une procession pour la fête-Dieu empruntant le portail occidental. La voûte en étoile, en gothique tardif, qui couvre le croisillon sud du transept date vraisemblablement aussi du dernier tiers du XVe siècle et marquait autrefois probablement l’endroit où se trouvait la tombe-reliquaire des saints Adolar et Eoban (actuellement dans l’église basse).
Le cloître se situe au sud de la cathédrale et se compose aujourd’hui de trois parties enserrant un petite cour intérieure. Les parties ouest et sud sont des ailes de cloître à vaisseau unique, de type classique. La partie nord fut jetée bas à l’occasion de la construction de la nef gothique. L’aile orientale est constituée d’une halle à deux vaisseaux, dite Halle de l’impératrice Cunigonde. Cette salle servait aux séances du chapitre et on peut supposer qu’elle fut érigée à peu près simultanément avec l’achèvement des deux tours entre 1230 et 1240. Les autres parties du cloître furent édifiées, et remaniées, section par section, du milieu du XIIIe siècle jusqu’au milieu du XIVe, et l’aile orientale fut voûtée après coup au milieu du XIVe. Par la suite, en particulier au XIXe siècle, les bâtiments formant le cloître furent encore profondément modifiés.
La chapelle Saint-Clément-et-Saint-Juste, s’inscrivant en éperon dans l’aile orientale, constituée d’une seule travée à voûte en étoile, close d’une abside semi-circulaire, fut terminée en 1455 et se trouve, à l’instar de la cathédrale elle-même, désaxée vers le nord.
Durant la Guerre de Trente Ans, la ville et l’église subirent plusieurs changements de propriétaire, et il fut même question de supprimer le chapitre et de le transmettre aux jésuites, ce que le chapitre toutefois réussit à empêcher. Entre 1697 et 1706 fut construit puis disposé dans le chœur l’imposant maître autel baroque, afin de donner un cadre plus fastueux aux cérémonies liturgiques et de bien signaler au-dehors la victoire obtenue par l’archevêque de Mayence sur la ville évangélique. Cependant, l’intérêt de province ecclésiastique de Mayence pour le diocèse s’amenuisant progressivement, l’archevêché ne fit guère exécuter de travaux d’entretien au cours des XVIIe et XIIIe siècles. Ainsi, après qu’en 1717 les combles des clochers eurent été détruits par un incendie, l’on se borna à poser un toit plat de fortune. Lors des guerres napoléonniennes, le Domberg, ainsi que le Petersberg, fut mué en une forteresse et la cathédrale fut utilisée comme écurie par les troupes françaises.
Sous l’effet des tirs d’artillerie lors des guerres de libération de 1813, le dense tissu bâti du Domberg, avec les curies épiscopales, fut tout entier détruit. Dissous une première fois en 1803, le chapitre de la cathédrale fut, dans le cadre de la sécularisation, supprimé à titre définitif en 1837, l’édifice allant désormais servir d’église paroissiale.
En 1828 fut lancé dans la ville d’Erfurt, devenue alors prussienne, un important programme de restauration et de transformation puriste, dans le cadre duquel l’ancien toit en croupe de style gothique tardif fut changé en 1868 en une toiture à pignon plus basse. Ces remaniements étaient largement terminés aux environs de 1900.
Pendant la Deuxième Guerre mondiale, si la cathédrale fut épargnée par les impacts directs de bombes, la toiture et les fenêtres du chœur furent néanmoins endommagées, en partie gravement, par des détonations à proximité. Les travaux de réfection durèrent jusqu’en 1949.
L’année 1965 vit à nouveau le début d’importants travaux de restauration. En 1968, 100 ans après sa construction, le toit néogothique avec la mosaïque de la vierge Marie sur le pignon occidental fut démoli et remplacé par une nouvelle toiture correspondant mieux à l’ancien comble gothique. La restauration de l’église fut poursuivie dans les années 1970 et 1980, pour s’achever en 1997. En 1994, l’ancienne collégiale Notre-Dame fut élevée au statut de cathédrale de l’évêché d’Erfurt restauré.