Medinę bažnyčią 1520 m. pastatė Polocko vaivados žmona Benigna Radvilaitė-Astikienė. 1530 m. Jurgis Astikas bažnyčiai dovanojo palivarką. 1587 m. bažnyčiai skirta daugiau turtų. 1655 m. ji sudegė.
1674 m. dar buvo laikina. Klebonijos palivarke (2 km nuo Gegužinės) kunigas Šiukšta 1735 m. pastatė kitą bažnyčią, kuri buvo gerai prižiūrima (1782), o parapinė suirusi (nuo 1812 m. parapinėje bažnyčioje pamaldų nebūdavo). XVIII a. veikė parapinė mokykla.
1852 m. pagal architekto Tomo Tišeckio projektą pastatyta nauja medinė bažnyčia. Apie 1889 m. Gegužinėje pradėta lietuviškai sakyti pamokslus ir laikyti pamaldas. Klebonas Jurgis Glodenis 1897 m. lietuviškus pamokslus panaikino ir lenkiškai nemokančių vaikų nekatekizuodavo. Žmonėms reikalaujant pamokslai lietuviškai pradėti sakyti 1902 m. 1911–1915 m. veikė Lietuvių katalikų blaivybės draugijos skyrius.
Naujos mūrinės bažnyčios pamatai pašventinti 1909 m. vasarą (šventino kunigas Juozapas Būčys). Iki 1915 m. buvo išmūrytos iš tašytų akmenų sienos, uždengtas stogas, bet karas sustabdė darbus. Statyba atnaujinta 1928 m. Dar nevisai įrengta bažnyčia 1932 m. pašventinta. Iš senosios bažnyčios 1933 m. pastatyti 2 aukštų parapijos namai. Naujos bažnyčios statyba rūpinosi Juozapas Būčys, klebonavęs Gegužinėje 1911–1928 m., Stasys Pupaleigis, čia klebonavęs 1928–1934 m.
1934–1939 m. Gegužinės klebonas buvo Nikodemas Švogžlys-Milžinas, Vilniaus krašto lietuvių visuomenės veikėjas, poetas, literatas. Po Antrojo pasaulinio karo parapijos klebonas Steponas Rudžionis 1946 m. suimtas ir už dalyvavimo pasipriešinimo veikloje nuteistas 25 metus kalėti. Mirė Vorkutos lageryje.