Kamajų dvaro savininkas Adomas Lukianskis-Paulavičius 1635 m. pastatė medinę bažnyčią. Jai paskyrė 4 margų sklypą, o 1650 m. – Duokiškio palivarką ir 3000 auksinų. Metrikų knygos rašytos nuo 1637 m. Samuelis Lukianskis-Paulavičius 1677 m. įkūrė altariją ir skyrė jai išlaikymą. Bažnyčia 1737 m. sudegė. Jos vietoje pastatyta kita medinė. 1774 m. įsteigta parapinė mokykla.
1820 m. bažnyčia perstatyta, pailginta. Šventorius apmūrytas. Kamajuose nuo 1820 m. gyveno (1824 m. vikaravo) poetas kunigas Antanas Strazdas (1763–1833, palaidotas Kamajų kapinėse). Kamajų klebonas Ignas Macevičius 1863 m. ištremtas į Orenburgą (1887 m. grįžo į Rygą). Vikaras Jonas Juozapaitis 1893 m. (už raginimą nesimelsti už carą) valdžios įsakymu dvejiems metams uždarytas į Kretingos vienuolyną.
1892 m. prašyta valdžios leidimo statyti naują mūrinę bažnyčią. Prašymas atmestas. Bažnyčią 1896 m. leido statyti konsistorija, kai valdžios leidimo nereikėjo. Pagal inžinieriaus Floriano Vyganovskio projektą 1897–1903 m. pastatyta dabartinė plytų mūro bažnyčia. Apie 1908 m. įrengti šv. Juozapo ir šv. Kazimiero vitražai (vitražistas Vladislovas Pšibitnevskis). Statyba rūpinosi klebonas J. Jokimas (palaidotas prie bažnyčios).
1908 m. įsikūrė „Saulės“ draugijos skyrius ir įsteigė biblioteką – skaityklą. 1908 m. įsikūrė Lietuvių katalikų draugijos blaivybės skyrius, kuris 1913 m. įrengė arbatinę. 1909 m. įsteigta „Saulės“ mergaičių mokykla. Klebono V. Velžio rūpesčiu 1912 m. pastatyta mūrinė klebonija. 1934 m. pastatyti vargonai.
1937 m. perstatyta prieglauda, įrengta susirinkimų salė. 1944 m. bažnyčia sužalota, nugriauti bokštai. Vėliau suremontuota, bokštų viršūnės neatstatytos. Klebonas Stanislovas Masilionis (1908–1955) 1945 m. suimtas, nuteistas 10 m. kalėti (į Lietuvą grįžo 1955 m.).