1806 m. Sudeikiuose pastatyta laikina bažnyčia ir pradėta statyti akmeninė bažnyčia. Baigta tik 1825 m. 1835 m. bažnyčios stogas buvo dengtas šiaudais, nes jaunesnysis Koziela-Poklevskis bažnyčios statybai neskyrė lėšų. Klėtis ir varpinė, bokšteliai bažnyčios priekyje ir gale buvo pastatyti valstiečių lėšomis. O klebonija, špitolė, kumetynas ir kiti ūkiniai pastatus – už parapijiečių aukas. Dvarininkai bažnyčiai dovanojo 2 valakus (apie 40 ha) Sudeikių kaimo žemės. XIX a. pradžioje veikė parapinė mokykla. 1822 m. bažnyčioje buvo apgedę 9-ių registrų vargonai. Užfiksuoti pasakojimai, jog bažnyčios statybai reikėję daug akmenų, jie vežti iš visų aplinkinių kaimų. Bažnyčios šventoriaus tvoroje esą net aukuro akmenų, atvežtų iš šalimais esančio Alkų kalno. 1825 m. pastatyta dabartinė klasicistinio stiliaus tinkuoto akmenų mūro bažnyčia. 1917 m. abiejuose stogo galuose uždėti mediniai bokšteliai su kryžiais. 1944 m. gerokai sužalota, vėliau suremontuota, iki 1955 m. uždėtas barokinis frontonas.