1387 m. pastatyta viena pirmųjų Lietuvoje bažnyčia, įsteigta parapija. Bažnyčiai turtų paskyrė Lietuvos didysis kunigaikštis Vytautas. Privilegijai dingus, ji patvirtinta 1525 m. Nemenčinės bažnyčia XVI a. viduryje buvo gana turtinga. Jai priklausiusioje žemėje buvo 81 valstiečių sodyba. Maskvos kariuomenė bažnyčią 1655 m. sunaikino, iki 1680 m. atstatyta. Per Šiaurės karą (iki 1706 m.) bažnyčia sudeginta. Po 1712 m. atstatyta. 1775 m. įkurta Šv. Rožančiaus brolija. XVIII a. pab.-XIX a. pradžioje veikė parapinė mokykla.
Nemenčinėje 1774–1790 m. klebonavo poetas Adomas Naruševičius, vėliau Lucko vyskupas. Nemenčinės žemės 1803 m. paskirtos Vilniaus universitetui, kuris klebonui mokėjo atlyginimą. 1807–1824 m. Nemenčinėje klebonavo gamtininkas, Vilniaus universiteto profesorius Stanislovas Bonifacas Jundzilas (1761–1847 m.), 1824–1840 m. – Florijonas Bobrovskis, 1882 m. Vilniuje išleisto lenkų – lotynų kalbų žodyno autorius.
1848–1855 m. vietoj 1842 m. sudegusios pastatyta dabartinė mūrinė bažnyčia. Statyba rūpinosi 1851–1857 m. klebonavęs Antanas Kitkevičius-Kikutis (1805–1857 m.), kuris ir palaidotas Nemenčinėje. Bažnyčią 1855 m. rugsėjo 20 d. konsekravo vyskupas Vaclovas Žilinskis.
Ne visi Nemenčinės parapijos kaimų gyventojai 1849 m. kalbėjo lietuviškai. XIX a. pamaldos laikytos ir pamokslai sakyti tik lenkų kalba. 1892–1895 m. Nemenčinėje vikaravęs Mykolas Masiulis bažnyčioje pradėjo vartoti lietuvių kalbą. Jį iškėlus, parapija toliau lenkinta. XX a. pradžioje dar buvo 20 lietuviškai kalbančių parapijos kaimų. Lietuvių kalba bažnyčioje pradėta vartoti 1939 m., atgavus Vilniaus kraštą. Bažnyčia 1947 m. apdegė. 1950 m. suremontuota.