Construcția bisericii suprapune un cimitir – dezvoltat probabil în jurul unei capele – din perioada secolelor XII-XIII. De asemenea, o serie de indicii sugerează faptul că pe amplasamentul acesteia a funcționat un edificiu de cult anterior, în stil romanic. Deschiderea șantierului bisericii actuale are loc la jumătatea veacului XIV, ulterior ridicării așezării de pe malul Someșului la rang de oraș liber (1316).
O inscripție datată în anul 1444 atestă momentul amplasării în timpanul portalului de vest a reliefului cu reprezentarea Sf. Arhanghel Mihail în luptă cu Balaurul. Aceasta din urmă suprapune imaginea celor trei steme ale regelui-împărat Sigismund de Luxemburg – cea de împărat romano-german, în centru, cea de rege al Ungariei, în stânga şi cea unificată, de rege al Ungariei, Boemiei şi al Germaniei, respectiv arhiduce de Austria, în dreapta. Momentul marchează încheierea etapei principale a edificării bisericii. În intervalul secolelor XV-XVI, pe fațada de vest sunt proiectate și parțial construite două turnuri. Diferite structuri construite ale bisericii au fost avariate în incendiile care afectează edificiul în anii 1498, 1665 și 1697. Turnul de nord, reconstruit în stil baroc între anii 1742 și 1744, este lovit de un fulger şi avariat de cutremurul din 1763. Funcţia acestuia va fi preluată timp de circa un secol de o clopotniţă din lemn, construită la sud de biserică. În amintirea epidemiei de ciumă care a afectat orașul, la 1747 este construită o poartă monumentală barocă în faţa portalului de vest al bisericii. Ulterior, aceasta va fi mutată în faţa bisericii romano-catolice Sf. Petru. Turnul actual, racordat faţadei de nord a bisericii, datează din anii 1837-1859.
Ridicată ca biserică a comunității romano-catolice, de care a aparținut până în anul 1545, aceasta va trece pe rând în uzul celei evanghelice, până în anul 1558, al celei reformate, până în anul 1566, al celei unitariene (exceptând perioada anilor 1603-1605, când aici vor oficia slujbe preoții iezuiți), până în anul 1716, moment când va fi redată romano-catolicilor.