Kunigaikštis Konstantinas Ostrogiškis Parudaminyje pastatytai stačiatikių cerkvei davė dirvų ir pievų Terešiškių apylinkėse. Po 1596 m. buvo unitų bažnyčia. 1662 m. ir vėliau Ašmenos pakamaris J. Ziemla iš Parudaminio unitų bažnyčios atėmė turėtas privilegijas, žemes. 1700 m. unitų bažnyčia dar tebebuvo.
Jonas ir Johana Horainai Parudaminio dvarą 1726 m. paskyrė Vilniaus moterų benediktinių vienuolynui. 1744 m. minima koplyčia. Benediktinės 1776 m. pasistatė naują koplyčią. Ją aptarnavo nuolatinis kunigas. Caro valdžia 1866 m. kunigo skirti neleido. 1867 m. koplyčia uždaryta ir nugriauta. Varpai perduoti Inturkės cerkvei.
1906 m. patvirtintas inžinieriaus A. Filipovičiaus-Duboviko mūrinės bažnyčios projektas. 1908 m. pastatyta medinė bažnyčia, 1922 m. – dabartinė mūrinė. 1925 m. įkurta parapija.