Pirmoji, medinė Romos katalikų bažnyčia Leliūnuose pastatyta 1698 m. Tačiau ilgesnį laiką parapijos nebuvo. Tuo metu Leliūnai priklausė Vyžuonų parapijai. Leliūnų dvaro savininkas Juozas Pomarnackas 1788 m. pastatė antrą medinę 12x28 m² ploto bažnyčią. Ji buvusi kryžiaus formos, bokštelyje kabojęs signatūrinis varpelis. Iš lauko pusės lentomis apmušta, viduje Šv. Juozapo su kūdikėliu Jėzumi altorius. Medinėje varpinėje kabojo trys varpai. 1793 m. įsteigta parapija, 1795 m. bažnyčiai dovanotas valakas žemės, vadinamos Starkiškiu. 1794 m. pradėtos rašyti metrikų knygos. 1867 m. pakeisti supuvę bažnyčios sienojai, pristatytos 2 koplyčios. Antroji bažnyčia supuvo, ir klebonas kun. Antanas Masaitis senos bažnyčios vietoje 1901 07 16 pašventino kertinį naujos mūrinės bažnyčios akmenį ir pamatus.

Dabartinė Leliūnų bažnyčia statyta 1901–1905 m. Ji mišrios architektūros su gotiškais, romaniškais ir to laiko moderniškais elementais. Projekto autorius - Pakalnių dvaro savininkas ir inžinierius Kulieša. Statė latvis Anzolis. Plytos degtos Leliūnų ir Sungailiškių dvaruose. Bažnyčios ilgis – 37,5 m, plotis – 21,5 m, sienų aukštis – 15 m, bokšto su kryžiais – 51 m. Dekoravo dailininkai Stakauskas ir Novakauskas. Didžiosios durys ąžuolinės, kitos – pušinės, langų rėmai geležiniai. Trys altoriai ąžuoliniai. Sakykla gotikinio stiliaus. 1913 m. įrengti dviejų klaviatūrų, 21 registro vargonai, pagaminti Karaliaučiuje Brunono Goebelio dirbtuvėje. Tai vieni pirmųjų pneumatinių vargonų Lietuvoje.

1931 m. žaibui trenkus į bažnyčios bokštą nukrito 3 varpai, iš jų 2 sudužo. Klebono Jono Gudonio rūpesčiu 1940 m. varpai perlieti. Per Antrąjį pasaulinį karą vienas varpas išvežtas.