Pirmoji medinė bažnyčia pastatyta 1563 m. Klebonas Legovičius (lenk. Legowicz) kartu su miestiečiais pastatė pirmąją medinę bažnyčią Užpaliuose. Lietuvos didysis kunugaikštis Steponas Batoras 1584 m. įsakė Užpalių savininkui laikyti kunigą ir nuo kiekvieno valako jam kasmet mokėti po grašį. Vėliau bažnyčiai dovanotas Germaniškio palivarkas. XVII a. pradžioje bažnyčia buvo perduota kalvinistams, tačiau netrukus grąžinta katalikams. Antroji medinė bažnyčia pastatyta 1651 m. ir 1653 m. pašventinta. Apie 1750 m. klebonas Petras Stasevičius pasenusią bažnyčią nugriovė ir jos vietoje pastatė naują medinę bažnyčią, nupirko jai Krimblių (Armališkių) palivarką. Nuo 1782 m. veikė parapinė mokykla. Per miestelio gaisrą 1783 m. liepą bažnyčia sudegė. Apie 1787 m. klebonas Adomas Legovičius su parapijiečiais pastatė naują medinę bažnyčią.

1885 m. prašyta leisti statyti naują mūrinę bažnyčią. Tik 1888 m. leidimas gautas iš Vilniaus generalgubernatoriaus. Klebono Kazimiero Kozminskio (1872–1914) ir parapijiečių pagal Ustino Golinevičiaus projektą pastatytą dabartinę bažnyčią 1898 m. konsekravo vyskupas Gasparas Cirtautas. Įrengti 16 registrų vargonai. Apie 1908 m. įsteigtas "Saulės" draugijos skyrius ir lietuviška mokykla, įkurtas parapijos knygynėlis. 1914 m. įsteigtas Lietuvių katalikų blaivybės draugijos skyrius. Dekano Jono Jarašiūno rūpesčiu 1925 m. išdažytas bažnyčios vidus. Ilgametis Užpalių klebonas Antanas Paurys (1885–1968; Užpaliuose nuo 1929 m.) suremontavo bažnyčią, pastatė altariją, rėmė Sibiro tremtinius. Bažnyčia istoristinė, turi neogotikos ir neoromaninio stiliaus bruožų, stačiakampio plano, dvibokštė. Vidus 3 navų. Yra 5 altoriai. Šventorius apmūrytas ažūrine plytų tvora. Jame stovi klasicistinė mūrinė varpinė (1847 m.).