Bereits um 1240 muss es eine Nikolaikirche gegeben haben; über ihre Gestalt liegen keine verwertbaren Informationen vor. Die Errichtung des heutigen Chores setzte um 1270 ein, die Vollendung der Ostteile erfolgte wohl Anfang des 14. Jh. Das Langhaus wurde unmittelbar danach und wahrscheinlich von Westen begonnen. Aufgrund der zahlreichen, zwischen 1330 und 1360/70 ausgeführten Wandmalereien und der in diesem Zeitraum erwähnten Seitenkapellen des Langhauses ist ein Abschluss der Arbeiten Mitte des 14. Jh. anzunehmen; möglicherweise unter Mitwirkung eines 1353 genannten Baumeisters Heinrich von Barth. Die südlichen Chorkapellen wurden wohl noch vor 1447 angefügt. Die Errichtung des Westbaus begann um 1300 zunächst als Einturm, er wurde seit etwa 1314-18 als Doppelturmfront weitergeführt. Zumindest einer der Türme wurde bis 1366 vollendet (Zerstörung eines Turmhelmes durch Sturm). Ein Brand im Jahre 1667 zerstörte die mittelalterlichen Turmhelme. Der Nordturm wurde mit einem Notdach geschlossen, der Südturm erhielt den heutigen barocken Helm. Mitte des 19. Jahrhunderts und 1891—1910 erfolgten umfassende Restaurierungen des Inneren (1890-94 Malerei im Chor freigelegt, 1909 im Langhaus und in den Turmhallen, zuletzt 1978-91)