I Stevns Kommune ligger den folkekirkelige medlemsprocent på 80 % og således over landsgennemsnittet på 73,8 % (2021). Kommunen omfatter 17 sogne fra Tryggevælde Provsti, der hører til Roskilde Stift. Sognene indgår i syv flersognspastorater og et etsognspastorat, Store Heddinge. Tryggevælde Provsti, som består af kommunerne Stevns og Faxe, har 25 præster og 28 menighedsråd, dvs. mange små sogne med eget menighedsråd.
Omkring midten af 1800-tallet var der tidlige vækkelser i Lille Heddinge i den sydlige del af kommunen. Senere opstod en grundtvigiansk frimenighed i Lyderslev Sogn med kirkeindvielse i 1887. I 1960 overgik frimenigheden til valgmenighed. To friskoler på egnen, Hellested Friskole og Stevns Friskole, er inspireret af den grundtvig-koldske skoletradition.
Indre Mission var til stede i Store Heddinge med missionshus opført i 1898 og besøg af flere indremissionærer. Formanden for Københavns Indre Mission, stiftsprovst R. Volf, fik i 1899 embedet i Store Heddinge, og en indre missionsk kreds fik for alvor vind i sejlene i byen. I mellemkrigstiden hørte en af præsterne i Store Heddinge altid til Indre Mission.
Det sociale kirkelige arbejde foregår i KFUM’s regi. KFUM’s Sociale Arbejde åbnede i 2012 Café Stevnen som varmestue for udsatte borgere i kommunen.