Verso il 1150 si diede inizio alla costruzione di una chiesa a tre navate, senza transetto e con due torri gemelle sulla facciata, poi rifatte fra il 1267 e il 1280 in seguito a un incendio. Questa chiesa fu consacrata solo nel 1228 dal vescovo Gebhard, all'Assunta.
Un incendio scoppiato nel 1621 danneggiò gravemente la chiesa, e sotto l'ambizioso prevosto Johann Michel Führer si decide di ricostruire l'edificio in un fastoso stile barocco. Viene contattato allora Jakob Prandtauer, l'architetto della scenografica abbazia di Melk, alla quale Führer si ispirava. Prandtauer inizia la costruzione nel 1721-22, concependo una struttura più alta, su due piani, e l'elevazione di una terza torre al centro della facciata. Ma i lavori si interrompono bruscamente nel 1739 con la fallita della diocesi e le dimissioni del prevosto.
Daniel Gran e Bartolomeo Altomonte eseguono la decorazione della volta, Thomas Friedrich Gedon dipinge gli altri affreschi. La chiesa sarà completata verso il 1750.
