Liczne pożary nawiedzające kościół wymusiły konieczność budowy nowej świątyni, co wykonano w latach 1412–1540. Powstała trzynawowa konstrukcja halowa długości 42 m, szerokości 25 m i wysokości 22 m, opięta od zewnątrz systemem przypór. Każda nawa liczy sześć przęseł i jest zakończona apsydą. Pierwsze trzy przęsła mają sklepienia krzyżowe, trzy następne – późnogotyckie sklepienia sieciowe. Odmienny kształt i wysokość wież kościoła wynika z faktu, że południowa, prostokątna wieża jest najprawdopodobniej pozostałością starej świątyni. Natomiast druga, niższa wieża została wzniesiona wraz z obecnym kościołem, a w jej formie widać już pierwsze zwiastuny architektury Odrodzenia. Renesans przyniósł również dobudowaną w 1574 r. do północnej nawy kościoła kaplicę V. Edelmanna. W XVII wieku, po ustaniu zarazy, w nastawie ołtarzowej złożono relikwie patronki miasta św. Pauliny.