I Vordingborg Kommune er 79,2 % af indbyggerne medlemmer af folkekirken mod 73,8 % på landsplan (2021). Kommunen omfatter Stege-Vordingborg Provsti, der hører til Roskilde Stift. Provstiet har 27 sogne fordelt på 14 pastorater med 22 sognepræster og 20 menighedsråd. Kommunen har mange små landsogne.
Salmedigteren N.F.S. Grundtvig blev født i Udby og virkede som kapellan i sin fars embede i Udby-Ørslev Sogne 1811‑13 og siden som præst i Præstø-Skibinge Sogne 1821‑22. Hans kirkelige anskuelse, trosbekendelsen (og ikke Skriften), afklaredes dog først senere, og den grundtvigianske vækkelse på egnen manifesterede sig især med præsterne Peter Rørdam i Mern Sogn og herefter F. Boisen i Stege Sogn på Møn. Boisens hustru, Eline Boisen, har i sine erindringer (påbegyndt 1856, udgivet 1985) givet et unikt indblik i, hvordan den både gudelige og politiske vækkelse invaderede præstehjemmet. Sønnen, politikeren Frede Bojsen, stiftede i 1866 Rødkilde Højskole (i dag: Rødkilde Teaterhøjskole). En grundtvigiansk leder på egnen var gårdejer Jens Olsen fra Snesere Sogn, som var en af hovedmændene bag højskolen i Brøderup i 1867, der i dag er efterskole med grundtvig-koldske rødder.
Den indremissionske bevægelse var især udbredt i Vordingborg, hvor missionshuset Bethania blev indviet i 1889, og i Præstø Sogn, der fik missionshuset Emaus i 1895. Markant i Præstø var den missionske præst J.E. Gjellebøl, som blev landskendt for sit skrift Spildte Guds ord paa Balle-Lars fra 1861, der siden blev til en talemåde. Dette skrift giver et indblik i tidsånden med Gjellebøls sjælesorg i forhold til den dødsdømte Lars fra Balle i Kalvehave Sogn.
I Vordingborg, Præstø og Stege eksisterede der i 1900-tallet et kirkeligt liv omkring KFUM/K med bl.a. soldaterhjem og missionskredse, som i dag tilsvarende udfolder sig omkring Folkekirkens Nødhjælps genbrugsbutikker m.m. I Vordingborg ligger Dansk Muslimsk Venskabsforening, grundlagt i 2016. Foreningens moské bruges på tværs af etniske grupper.
