Allerede i 1830’erne kan vi finde de første kim til en katolsk menighed på Næstvedegnen. Holmegaard Glasværk sendte i disse år bud efter glasarbejdere fra Böhmen, og vi ved med sikkerhed, at fem af disse den 28. oktober 1835 blev viet af en katolsk præst til deres kærester, som de havde bragt med fra deres hjemland.
Indtil religionsfriheden blev indført med Grundloven af 5. juni 1849, var det som hovedregel ikke tilladt at holde offentlige katolske gudstjenester i Danmark. Der fandtes således på daværende tidspunkt kun enkelte katolske præster i landet, som var knyttet til de udenlandske ambassader. Det var en af disse præster, der forrettede vielsen, som fandt sted i inspektørboligen.
Industriens opblomstring i slutningen af århundredet førte endnu flere gæstearbejdere til egnen, hovedsageligt polakker, og i 1895 blev der indrettet et egentligt kapel, Sct. Franciskus-kapellet, på glasværket. Kapellet er bevaret som museum og kan stadig beses på stedet.
Regelmæssige gudstjenester blev afholdt fra 1899 i et nyindrettet kapel på Store Møllegård beliggende på Præstøvej. Kapellet brændte i 1903. Herefter blev alle gudstjenester afholdt i præstegården Villa Alfa, indtil den nuværende kirke, Vor Frue Kirke, stod færdig i 1926. Grundstensnedlæggelsen fandt sted den 16. august 1925, og kirken blev indviet den 29. maj 1926.
Næstved sogn var dog allerede blevet oprettet som selvstændigt sogn den 18. maj 1916. Fra 1916-21 var det præmonstratensere fra Vejle, der betjente det ny sogn. I 1922 overtog redemptoristene, og det var den første redemptoristpræst, pater Peter Damian Steidl, der blev Vor Frue Kirkes ‘bygherre’ med Johannes Tiedemand-Dal som arkitekt. Pater Steidl havde stået for byggeriet af ordenens Skt. Albani Kirke i Odense, som blev indviet i 1908, og han havde overskredet budgettet med over 100%, hvilket bestemt ikke af ordenen gik upåtalt hen.
Nu, hvor han, mærkeligt nok, igen blev ‘kirkebygger’ passede han på, – nogle sagde, at han i Næstved havde bygget for småt. Det planlagte kirketårn blev droppet, men, som det havde været tilfældet i Odense, blev også Vor Frue kirkes gyldne alter og korsvejsstationerne leveret af billedskærer Konrad Martiner fra St. Ulrich i Tirol.
I 1930 begyndte man at holde gudstjeneste i Vordingborg, og i 1939 opførtes en kryptkirke med en større kirke for øje. Den kom først i 1994 og kom kun til at eksistere til 2015, hvor den blev nedlagt.
I 1974 blev Vor Frue Kirke restaureret af arkitekt Ingemann Arthur-Nielsen, som tilpassede redemptoristernes tre kirker i Danmark til 2. Vatikankoncils liturgiske bestemmelser. Som tak blev han optaget som ‘oblat’ i deres kongregation.