Pakalnių dvaro savininkas Antanas Kulieša apie 1762 m. pastatė medinę bažnyčią. Jos vietoje kunigas Jurgis Kazlauskas su parapijiečiais 1906 m. kitą medinę bažnyčią. Ji buvo Leliūnų parapijos filija. 1928 m. įsteigta parapija. Bažnyčia buvo sudėtingos kompozicijos, nepanaši į tradicinę, su trisiene apside, 2 bokšteliais, žemesnėmis zakristijomis. Vidus 3 navų. Šventoriaus tvora akmenų mūro.

1992 metais bažnyčia atremontuota. Bet štai 2000 m. balandžio 25-ąją tikintieji savo bažnytėlės neteko. Gaisras ankstyvą rytmetį iki pat pamatų suniokojo medinę bažnyčią. Niekuo negalėjo pagelbėti nei atskubėję ugniagesiai, nei sulėkę parapijiečiai - ugnies liežuviai be jokio gailesčio rijo medines sienas, lubas, papuošimus, šventųjų skulptūras, bažnytinius reikmenis. Vėliau žmonės, valydami gaisravietę, rado tik keletą religinio turinio knygų likučių, apdegusios bažnyčios istorijos puslapius. Ranka rašytos istorijos pirmajame puslapyje buvo žodžiai: "Bažnyčios ilgis – 25 metrai, platumas – 12 metrų, aukštumas oro pusėje nuo pamatų iki bažnyčios šelmenio – 10 metrų. Bažnyčia nuo ugnies neapdrausta...". Pakalniškiai iki šiol įsitikinę, kad jų bažnyčia buvo padegta tyčia, esą net matėsi kažkokio skysčio liekanų, jautėsi benzino ar dyzelinio kvapas. Utenos policijos komisariato pareigūnai tyrė šį įvykį, tačiau įtariamųjų dėl padegimo nepavyko rasti. Gaisro priežastys taip ir liko neišaiškintos.

Gyventojai tuoj pat po gaisro rinkosi prie bažnyčios ir tvarkė aplinką, vežė nuodėgulius, nupjovė apdegusius medžius. Jų mintyse buvo vienintelė svajonė - turėti Pakalniuose naują bažnyčią. Tam sumanymui pritarė ir Leliūnų Šv. Juozapo parapijos klebonas kun. Kostas Balsys, kuris aptarnaudavo ir Pakalnių parapiją. Visi sudegusios bažnyčios tvarkymo darbai būtų kainavę apie 20 tūkstančių litų, tačiau jie atlikti veltui - parapijiečiai mielai ėjo į talkas, atvažiuodavo talkininkai ir iš Leliūnų, Utenos. Daug padėjo Leliūnų seniūnija. Sutvarkius gaisravietę, buvo paskelbtas bažnyčios atstatymo projekto konkursas, pradėtos rinkti aukos, išrinktas bažnyčios atstatymo komitetas. Aukų rinkėjai važinėjo po kitas parapijas, dalyvaudavo religinėse šventėse kitų miestų bažnyčiose. Užjausdami pakalniškius, naujosios bažnyčios statybai pinigus aukojo anykštėnai, uteniškiai, molėtiškiai, zarasiškiai, panevėžiečiai ir kitų vietovių gyventojai. Klebono kun. K.Balsio rūpesčiu, padedant parapijiečiams, laiminant Panevėžio vyskupui Juozui Preikšui, 2000 m. rugpjūčio 6-ąją prasidėjo naujosios Pakalnių bažnyčios statyba. Kertinį akmenį tuomet padėjo Seimo pirmininkas prof. Vytautas Landsbergis, o pašventino vysk. J. Preikšas. Pirmąsias šv. Mišias klebonas aukojo ką tik iškilusioje, bet dar be langų, durų bažnyčioje gruodžio 25-ąją, antrąją šv. Kalėdų dieną.

Ilgą laiką Pakalnių žmonės didžiavosi, kad jų medinė bažnytėlė – viena seniausių Utenos krašte, o dabar didžiuojasi, kad bažnyčia yra pati naujausia.