1503 m. Perlojos bažnyčios apdovanojimo dokumente nurodyta, kad ji statyta Lietuvos didžiojo kunigaikščio Vytauto, yra Daugų filija. Apie 1777 m. pastatyta maumedžio rąstų bažnyčia, įkurta parapija. 1866 m. caro valdžiai uždarius bažnyčią, tikintieji 1875, 1882 ir 1892 m. prašė ją grąžinti, bet valdžia nesutiko.
1903 m. patvirtintas naujos bažnyčios projektas. Valdžia statyti neleido, tik 1906 m. grąžino uždarytąją; atkurta parapija. 1909 m. patvirtintas mūrinės bažnyčios projektas (aut. M. Bergas), leidimas statyti gautas tik 1914 m. Klebonas Pr. Cibulskis su parapijiečiais (už 140 000 litų) 1928–1930 m. pastatė dabartinę mūrinę bažnyčią (inž. Vaclovo Michnevičiaus projektas). Ją 1930 m. konsekravo vyskupas Juozapas Kukta. Vokietijos okupacijos metais bažnyčią dekoravo Varšuvos meno akademijos profesorius J. Hopenas (vokiečių belaisvis).
1944 m. per Perlojos gaisrą sudegė klebonija.