Kostel sv. Mikuláše byl postaven ve střední části Dolního trhu (dnešní náměstí svobody) v 1. polovině 13. století jako fi liální kostel ke kostelu svatého Jakuba. Podle archeologických průzkumů zde pravděpodobně původně byla kovářská dílna. V roce 1231 Václav I. potvrdil, že kostel nemá křestní, pohřební a ani farní právo, jednalo se o první písemnou zmínku o kostele. Ve 14. století byla ke kostelu na jeho jižní straně vybudována strážnice. Rektory kostela byli například Jan, Petr Wolkenstein, Albert de Cross, Tomáš, Mikoláš Polák. V polovině 17. století kostel sloužil jako provizorní kapucínský hospic, protože ten stávající byl zničen Švédy. Na začátku druhé poloviny 17. století byl kostel obnoven a byla k němu ze severní strany postavena budova městských vah. Barokní podobu dostal kostel v roce 1780 od Františka Antonína Grimma. Za vlády Josefa II. byl však kostel zrušen a sloužil jako skladiště. V letech 1869-1870 byl kostel spolu s přilehlými budovami zbořen za účelem „zkrášlení Velkého náměstí“. Náhrobní kameny z kostela zasazeny do zdiva Moravské zemského muzea na Biskupském dvoře a sochy z průčelí kostela byly přesunuty na průčelí kostela svaté Máří Magdalény na dnešní Františkánské ulici. 

 

Dne 19. prosince 1944, během bombardování Brna USAAF, byla zasažena i oblast bývalého kostela a městských vah. Kostel měl jednu loď o čtvercovém půdoryse 10,3×10,3 m. Presbytář byl umístěn na východní straně. Presbytář byl obdélníkový 9,5 na 5,6m a byl ukončen pěti zdmi osmiúhelníku. Presbytář osvětlovalo šest gotických oken s lomeným obloukem. Gotická okna byla i na jižním průčelí kostela. Kostel měl také vnější opěrný systém. Kostel měl vysokou střechu a trojúhelníkový štít na východní straně. Jak vypadal interiér kostela, není zcela tak jasné. Prostor lodi byl pravděpodobně zaklenut valenou klenbou a prostor presbytáře klenbou žebrovou o dvou polích. 

 

Archeologické průzkumy kostela proběhly v letech 1964–65 a roku 2000. V současné době půdorysný obrys kostela připomíná mosazná linka v dlažbě náměstí a mosazná plaketní deska umístěná rovněž na dlažbě náměstí v místech, kde se nacházel presbytář.