Debeikių koplyčioje 1769 m. leista laikyti pamaldas. Steigiamai parapijai dvaras paskyrė 1,5 valako žemės, 1785 m. dovanojo 2 400 sidabrinių rublių. 1799 m. pastatyta medinė bažnyčia (pašventinta 1801 m.). Joje buvo 3 altoriai. Nuo 1804 m. veikė parapinė mokykla. Debeikių bažnyčios metrikų knygos rašytos nuo 1789 m.
Dabartinė mūrinė bažnyčia pastatyta 1906–1913 m. klebono Povilo Šimkevičiaus, vėliau klebono Domininko Mikšio rūpesčiu (už 61410 rb) 1912–1913 m. pastatyta parapijos salė. 1918 m. įsisteigė pavasarininkų kuopa. Vyskupas Pranciškus Karevičius 1921 m. bažnyčią konsekravo. Į Rusiją 1915 m. išvežti 3 varpai ir negrąžinti. 1924 m. Kaune nuliedinti 2 varpai, 1926 m. nupirktas trečias. 1928 m. įrengtos reljefinės Kryžiaus kelio stotys (dail. Vladas Čižauskas), pastatyti vargonai. 1938 m. bažnyčia išdažyta.
Debeikiuose 1920–1947 m. klebonavo Kazimieras Mikelinskas (1889–1957). Jis 1947 m. ištremtas į Sibirą. Į Lietuvą grįžo 1957 m.; palaidotas Debeikių kapinėse. 1950 m. suimtas ir nuteistas 10 m. klebonas Jurgis Šimonėlis. 1973–1992 m. klebonavo Alfonsas Gražys (1923–1992).
Klebonas Kazimieras Mikelinskas, kurio gyvenimo kelias buvo paženklintas tremties kančia, paliko ryškų pėdsaką parapijiečių širdyse. Jo sugrįžimas iš Sibiro tapo tikra dvasine švente, o kapavietė Debeikių kapinėse iki šiol lankoma kaip pagarbos ženklas ištikimybei Dievui. Bažnyčios varpai, kurie pakeitė per karą prarastus senuosius, turi savitą skambesį, kviečiantį bendruomenę susitelkti. Ši šventovė yra tarsi dvasinis švyturys, saugantis vietos žmonių viltis ir maldas. Net ir sunkiausiais laikais, kai bažnyčia patyrė įvairių suvaržymų, ji išliko vieta, kurioje žmogus galėjo rasti ramybę ir atgaivą savo sielai. Tai vieta, kurioje kiekvienas akmuo mena bendruomenės vienybę ir nepalaužiamą tikėjimą.