Pirmā zināmā Baltinavas katoļu baznīca celta 17.gs. otrajā pusē, 1695.gadā to iesvētīja bīskaps Nikolajs Poplovskis. Tā bijusi koka celtne. Baznīcas uzturēšanai esot piešķirtas 249 desetīnas un divi ciemi - Silagaiļi un Supāni. Baznīca atradās 2,6 km no Baltinavas, Keišu sādžā.

Otrā koka baznīca celta pašā Baltinavā 1769.gadā. 1774.gadā, Jaunavas Marijas pasludināšanas godam, to iesvētīja Ludzas dekāns Poslauskis. Koka baznīca atradās tagadējās mūra baznīcas priekšā - altāris bija tur, kur tagad ir baznīcas tornis, bet   gala ieeja un torņa daļa - pretī vārtiņiem, kas ved uz plebāniju.

Pamazām draudze pārauga baznīcu un tā kļuva par mazu. Tāpēc prāvests Andrejs Sviklis 1909.g. Baltinavā uzsāka celt šķeltu akmeņu mūra baznīcu. Viņš sagatavoja visus materiālus jaunās mūra baznīcas celšanai: akmeņus, kokus, dēļus, kaļķus. Baznīcu uzbūvēja tikai līdz logiem, jo 1914.g. iesākās pasaules karš un darbi bija jāpārtrauc. Kara laikā sagatavotie koka materiāli tika izvazāti, pazuda. Vecuma un nespēka dēļ Sviklis pēc kara vairs neuzņēmās turpināt baznīcas celšanu. 1919.g. viņu pārcēla uz Pušmucovas draudzi, bet par Baltinavas prāvestu kļuva Pēteris Gadzāns. Baznīcu nobeidza celt Vitālijs Trepša 1931.gadā. Šajā gadā Baltinavā notika bīskapa J.Rancāna vizitācija un viņš arī iesvētīja tikko uzcelto baznīcu. Baznīca ir 39 m gara un 15,5 m plata, krustavietā platums - 20 m. Tā ir trīsnavu telpa, ar flīžu grīdu. Baznīcas solos var novietoties 180 cilvēku.

Baznīcā atrodas seni sakrālās mākslas darbi. Vissenākā ir Jaunavas Marijas glezna, kas gleznota 17.gs. Tā ir gleznota uz ādas, kura uzstiepta uz koka pamatnes. Šī glezna ir vēl no pirmās baznīcas. Lielā altārglezna ir mākslinieka St. Zaleska darbs, tā darināta 1882.gadā. Svēto Antona un Jāzepa gleznas darinājis mākslinieks Kalvāns. 18. gs. darinātas koka figūra „Ecce Homo” („Lūk, cilvēks”) un četru apustuļu - Pētera, Pāvila, Jāņa un Andreja tēli.

Otrajā pasaules karā baznīca stipri cieta. To atjaunoja prāvests Alfons Misjuns, kas te nodzīvoja 17 gadus. Viņa darbības laikā ap baznīcas dārzu uzcēla metāla žogu. Ādolfs Tarbunass izraka aku, iegādājās liturģiskos tērpus, jaunus solus un ērģeles. Priesteris Ivars Babris ar bīskapa Jāņa Buļa svētību darbu Baltinavā uzsāka 2002.gada oktobrī. Pa šiem gadiem ir uzcelta draudzes māja, 2006.gada vasarā baznīcai, kuras jumta platība ir 1000 kvadrātmetru, uzklāts jauns skārda jumts. Veikta arī altāra telpas rekonstrukcija, kas ļauj priesterim svētās Mises celebrēt, stāvot ar seju pret tautu (agrāk - ar muguru). Tāpat baznīcas altāra telpa ieguvusi divas katedras: Svēto rakstu lasīšanas un bīskapa katedru.

2018.gadā baznīcā uzstādīti jauni digitāli zvani, kurus iesvētīja ceturtajā adventes svētdienā. No Polijas atvesti četri skaļruņi, kas saslēgti ar vadības centru, un spēj atskaņot apmēram 150 melodijas.

Baltinavas draudzē vēl kalpojuši: Andrievs Sviklis (1908-1919), Pēteris Gadzāns (1919-1931), Vitālijs Trepša (1931-1934), Izidors Livčāns (1933-1935), Jānis Ostrovskis (1935-1937), Pēteris Apšenieks (1937-1941), Kazimirs Lielbārdis (1942-1948), Gregors Zirnis (1948-1950), Broņislavs Kokins (1950-1951), Alfons Misjūns (1951-1968), Ādolfs Tarbunass (1968-1976), Jānis Svilāns (1976-1996), Alberts Budže (1996-2002), Ivars Babris (2002-2007), Sergejs Ivanovs (2010-2011), Ivars Vigulis (2012-2015), Staņislavs Prikulis no 2012.gada