Im letzten Drittel des 12. und zu Beginn des folgenden Jahrhunderts entstand über dem Grundriss des Vorgängerbaus wiederum ein dreischiffiger, um ein Querhaus erweiterter Kirchenbau. Aus dieser Zeit stammen auch die beiden Rundfenster am Querhaus - das eine im Norden über der Galluspforte in Gestalt eines Glücksrads und das südliche in Form eines Davidsterns. Der Chor mit offenem Umgang und den bemerkenswerten Figurenkapitellen sowie die Friese in der Krypta und an der Aussenseite des Chors entstanden Ende des 12. Jahrhunderts. Eine Altarweihe in der Apsis ist für das Jahr 1202 unter Bischof Lüthold I. überliefert. Der Bau wird von mächtigen Pfeilerbündeln getragen. Die Wände des um 1225 vollendeten Langhauses zeigen eine dreizonige Doppeljochgliederung. In der untersten Zone führen Spitzbogenarkaden in die Seitenschiffe, während die um das Kircheninnere laufenden Triforien sich anhand von Rundbögen in die begehbare Emporenzone öffnen.

Von dem damals an der Südseite der Kirche angebauten grossen Kreuzgang sind heute noch vier Joche (Gang von der Südseite des Chors zum Eingang der Katharinakapelle) erhalten. In der 2. Hälfte des 13. Jahrhunderts, vermutlich nach einem Brand im Jahr 1258, wurde der westliche Eingangsbereich umgestaltet: Der Georgsturm erhielt ein drittes Geschoss und der gegenüberliegende Martinsturm entstand in gleicher Höhe bis zur heute umlaufenden Brüstung, dazwischen zeigt sich die Fassade mit der bildhauerisch reich ausgestatteten gotischen Portalanlage und der darüberliegenden Partie mit grossem spitzbogigem Masswerkfenster. Die Tympanonreliefs der Portale wie auch die Marienfigur an dem Mittelpfeiler wurden 1529 im Bildersturm zerstört. Ebenfalls in der 2. Hälfte des 13. Jahrhunderts begann man einzelne Grabkapellen an die Seitenschiffe anzufügen.