czasem też zwana Tumem Adalberta – niem. Adalberto-Dom) nawiązuje do inicjatora jej wzniesienia – cesarza Henryka II, późniejszego świętego patrona miasta. Kościół został ufundowany przez Henryka II i jego żonę Kunegundę i konsekrowany w ich obecności 11 października 1019 przez Adalberta. Nosząca wezwanie Najświętszej Marii Panny budowla nie miała krypty, co wykazały wykopaliska prowadzone w latach 1973/1974. Około końca XI w. po zachodniej stronie wzniesiono wieżę z wapienia i mułowca. Mury te zachowały się i tworzą dolną część dzisiejszej wieży północnej (wieży św.Jerzego; Georgsturm). Katedra Henryka nie posiadała wieży po stronie południowej. W 1185 katedra spłonęła.
Katedra późnoromańsko-gotycka Dzisiejsza katedra opiera się głównie na budowli późnoromańskiej. Na fundamentach wcześniejszej budowli powstał kościół trójnawowy wzbogacony o transept (nawę poprzeczną). Chór był już ukończony w 1202 (poświęcenie głównego ołtarza przez biskupa Lütholda I), zaś nawy w 1225. W 1258 katedra została uszkodzona przez pożar. Prawdopodobnie po pożarze podwyższono Wieżę św. Jerzego do trzech kondygnacji, zaś w południowo-zachodnim narożniku dobudowano symetryczną do niej Wieżę św. Marcina.