Seniausia žinoma Valkininkų bažnyčios 1555 m. fundacija. 1611 m. inventoriuje minima prie turgavietės naujai pastatyta bažnyčia. 1635–1650 m. Valkininkuose pastatytas mūrinis vienuolynas su bažnyčia.
1655 m. parapinė bažnyčia sudegė, netrukus atstatyta. Vietoj 1772 m. sudegusios parapinės bažnyčios pastatyta laikina, kurią 1818 m. sausio 17 d. audra sugriovė. Pamaldos perkeltos į kapų koplyčią. Nuo 1777 m. veikė parapinė mokykla.
Parapinei bažnyčiai 1822 m., be jurisdikos miestelyje, priklausė Kuklių ir Puodžių kaimai. Vienuolynas turėjo jurisdiką Valkininkuose ir Kuršių kaimą. Rusijos valdžia vienuolyną 1832 m. uždarė ir pavertė kareivinėmis. Vienuolyno bažnyčia 1832–1837 m. naudojosi parapijiečiai. Po 1837 m. valdžia ją pertvarkė į stačiatikių kariuomenės cerkvę, 1883 m. perstatė į viešą cerkvę. 1941–1944 m. čia buvo karo belaisvių stovykla. 1944 m. hitlerininkai pastatą susprogdino.
1822–1837 m. pastatyta dabartinė mūrinė bažnyčia. Ją 1854 m. konsekravo vyskupas Vaclovas Žilinskas. Dar 1881 m. prašyta leidimo padidinti parapinę bažnyčią. Valdžia neleido, o kleboną V. Živoronoką už aukų rinkimą iškėlė iš Valkininkų. 1885 m. parengtas naujas bažnyčios padidinimo projektas. Vėl neleista statyti, nes bažnyčia savo išvaizda būtų nustelbusi stačiatikių cerkvę. 1895–1898 m. bažnyčia padidinta.
Valkininkuose 1884–1892 m. klebonavęs Silvestras Gimžauskas (1844–1897) skųstas valdžiai dėl lietuviškos spaudos platinimo, dėl jo nepageidautinos įtakos valdinei mokyklai. Jam buvo iškeltos kelios bylos. Valdžiai pareikalavus S. Gimžauskas iš Valkininkų pašalintas. Nuo 1918 m. klebonavęs Jonas Karvelis (1874–1933) Lenkijos valdžios persekiotas, 1927 m. suimtas ir ištremtas į nepriklausomą Lietuvą.
1946–1949 m. klebonavęs Stanislovas Kakarieka persekiotas, baustas už vaikų katekizaciją. Klebonui Algimantui Keinai valdžia 1970 ir 1973 m. trukdė remontuoti bažnyčią.