Pirmoji bažnyčia pastatyta XV a. antrojoje pusėje. Anykščių klebonas 1500 m. bylinėjosi su dvaro vietininku dėl dešimtinės iš Kavarsko dvaro. 1507 m. nustatytos klebono žemės ribos. XVI a. viduryje Anykščių bažnyčia buvo viena turtingiausių Vilniaus vyskupijoje. Klebonijos valdose būta 100 kiemų. Per 1566 m. miestelio gaisrą bažnyčia sudegė, netrukus atstatyta.
1671 m. vėl sudegė, iki 1677 m. atstatyta. Anykščių klebonijai 1673 m., be jurisdikos miestelyje, priklausė Elmininkų palivarkas, Kalvelių, Liudiškių, Medžiuolių, Migonių, Miliūnų, Papiškių kaimai. Kunigo Jono Domininko Lopacinskio (1762–1778 m. Žemaičių vyskupas) ir kunigo Tado Milašiaus rūpesčiu 1757–1768 m. pastatyta vienabokštė mūrinė bažnyčia. Ji buvo kryžiaus plano, turėjo 5 altorius.
1823 m. pastatyta mūrinė varpinė. Anykščių parapijoje 1858–1862 m. ypač propaguota blaivybė. Prekybininkai ir smuklininkai kleboną Ferdinandą Stulginskį dažnai skundė caro valdžiai. F. Stulginskiui 1863 m. pabaigoje atimtas kunigo titulas, dvarininko luomas, konfiskuotas turtas. Jis 8 m. išsiųstas į katorgą (mirė 1892 m. Smolenske). Kunigas J. Kelpša 1864 m. taip pat ištremtas į Sibirą (1871 m. grįžo į Liepoją).
1889 m. parengtas bažnyčios padidinimo projektas. Valdžia neleido jos perstatyti. 1896 m. leidimą davė konsistorija. Nutarta bažnyčios nedidinti, bet statyti naują. 1898 m. patvirtintas Nikolajaus Andrejevo naujos bažnyčios projektas (sąmatinė vertė 87 090 rb). Klebono Ferdinando Ūselio, vėliau klebono Juozapo Vembrės ir parapijiečių rūpesčiu bei lėšomis 1899–1909 m. pastatyta dabartinė mūrinė bažnyčia. Varpinė nugriauta. Bažnyčią 1914 m. konsekravo vyskupas Pranciškus Karevičius.
1908–1914 m. veikė „Saulės“ draugijos skyrius. Per Pirmąjį pasaulinį karą vokiečiai susprogdino bokštų viršutines dalis. Jos griūdamos sužalojo stogą ir skliautus. 1917 m. pristatyti mediniai bokštai.
Anykščiuose 1922 m. įsteigtas Šv. Kryžiaus seserų kongregacijos skyrius, pastatytas vienuolynas (fundatorės – Zosė Jokūbauskaitė ir Zosė Viesčiakaitė; veikė iki 1938). Vienuolyne įrengta koplyčia. Seserys širdietės savo namuose įsteigė pradinę mokyklą. Kilus 1928 m. gaisrui, sudegė didysis altorius, parapijos archyvas. Klebono Juozapo Norvilos iniciatyva atstatyti bokštai, didysis altorius, išdažyta bažnyčia.
Vienas žymiausių Anykščių klebonų buvo daktaras Juozapas Čepėnas (1880–1976), lietuvių spaudos bendradarbis. Prieš Antrąjį pasaulinį karą jis suremontavo kleboniją; 1940–1941 ir 1951–1954 m. kalėjo.