Původní kostel sv. Štěpána z 1. poloviny 12. století vznikl těsně vedle tehdejšího města. Přibližně za sto let byl nahrazen pozdně románskou trojlodní stavbou, ze které se zachovaly Obří brána a obě věže, zvané pohanské. Ve 14. a 15 století musela tato stavba ustoupit mohutnému gotickému dómu, jehož zvětšené rozměry již počítaly s příštím založením biskupství. Zvláštností je vysoký vnitřek, obrovská střecha, oddělené umístění věží, které se od země až po vrchol zužují. Ve druhé světové válce byl chrám silně poškozen požárem. Dnes jsou již veškeré škody odstraněny a střecha a varhany nahrazeny novými.