Na místě, kde dnes stojí kostel, původně vyrůstal románský kostelík postavený v roce 1136. Z té doby se dochoval jen zlomek – zdivo z pískovcových kvádrů, které tvoří dnešní sakristii.

Nový chrám sem přinesl arcibiskup Arnošta z Pardubic kolem roku 1350. Na stavbě se podílela dvorská arrasovská stavební huť. Postupně zde vyrůstal gotický kostel s pětiboký presbytářem a bazilikálním trojlodím. Na konci 14. století za arcibiskupa Olbrama III. ze Škvorce si kostel získal dominantní západní průčelí se dvěma věžemi.

Dějiny костела byly série těžkých zkoušek. V roce 1421, když husité obléhali město, kostel vypálili. Při tom zahynulo zhruba dvě stě lidí, kteří zde hledali ochranu. Oprava přišla v roce 1457, ale o padesát let později kostel znovu vyhořel a byl obnoven v pozdě gotickém stylu. V 17. století jej čekaly pozdně renesanční přestavby – zvýšeny byly boční lodě a trojlodí bylo pokryto novými lunetovými klenbami.

Zásadní změnu přinesl barok. Jan Josef Wirch vedl mezi roky 1765 až 1776 radikální barokní přestavbu. Původní gotické věže byly sníženy, průčelí překryto novou podobou s jedinou středovou věží. Stavba se protahovala, ale charakter gotické baziliky byl navždycky změněn.

Dvacáté století přineslo postupný úpadek stavby. Po opravě v roce 1880 se v roce 1905 rozhodlo o zásadní obnově. Architekt František Mikš navrhl radikální regotizaci, kterou ale Centrální komise pro zachování památek zamítla. Schválený plán byl mírnější a generální oprava se uskutečnila v letech 1912–1913. Následovaly další opravy v 1935, 1992–1994, 2000, 2004, 2007 a naposled v 2011–2012.

Dnešní stavba o rozměrech zhruba 37 × 21,5 metru ukazuje vrstvení stylů. Zvenku ji strukturují gotické opěráky. Průčelí je trojdílné s jónskými sloupy – ve výklenkích jsou sochy svatých (Ludmila, Václav, Jan Křtitel, Gotharda) z roku 1913 od sochaře Štěpána Zálešáka. Interiér překvapí: boční lodě jsou odděleny arkádami na osmibokých sloupech, presbytář má gotickou křížovou klenbu se žebry, kterou doplňuje renesanční lunetová klenba v hlavní lodi se zbytky původních gotických konzol.

Vedle kostela stojí historická zvonice. Původní zvonica byla zničena v roce 1421 spolu s kostelem, ale v letech 1578–1585 ji nahradil český brodský kamenický mistr Pavel novou renesanční zvonnicí s cibulovitou bání. Nástavbě se v 18. století změnily detaily – báň zmizela a dlátkovaná střecha ji nahradila. Po generální opravě v roce 2011 je zvonice zpřístupněna veřejnosti.

Kostel je od roku 1958 chráněn jako kulturní památka a stále slouží věřícím. Jeho postupné proměny – od románských základů přes gotický chrám k baroknímu vzhledu – činí jej jedinečným svědkem českých dějin.