Původně farní kostel svatého Mikuláše byl založen společně s městem ve 13. století poblíž náměstí Přemysla Otakara II. Poprvé byl přestavován v první polovině 16. století. Roku 1641 byl při požáru města až na obvodové zdi zničen. Během necelých deseti let byl obnoven, koncem 17. století byl ještě upraven průčelní štít Jakubem de Maggi. V kostele je hodnotné vybavení převážně ze 17. a 18. století, umístěné zde v souvislosti s přeměnou na katedrální kostel.
Ke kostelu byla v první polovině 18. století přistavěna barokní kaple Smrtelných úzkostí Páně. V kupoli kaple je nástropní malba Smrt Panny Marie od J. A. Schöpfa z doby po roce 1729.