Næstved Station blev etableret i forbindelse med anlæg af Sydbanen Roskilde-Køge-Næstved-Vordingborg-Masnedsund i 1870. Jernbanen Slagelse-Næstved kom til i 1892, og i 1900 førtes Præstø-Næstved Banen ind på stationen fra syd og endelig åbnedes den dobbeltsporede jernbane Ringsted-Næstved i 1924.
I begyndelsen af 1890'erne anlagdes et såkaldt militærspor, der forbandt sydbanen med Slagelsebanen, så tog kunne passere mellem disse baner uden at køre ind og vende (rebroussere) på Næstved station. Ved anlægget af strækningen Ringsted-Næstved blev militærsporet afbrudt, men der blev skabt mulighed for om nødvendigt at ilægge sporskifter og sporkrydsning.
Stationsbygningen opførtes under ledelse af arkitekt Charles Abrahams - der er sket løbende udbygning af den oprindelige banegårdsbygning, i 1899 og igen i 1921 under ledelse af arkitekt Sigurd Christensen. Ved ombygningen i 1940-1943 fik bygningen sit nuværende ydre, idet den lave sydlige del forhøjedes til 2½ etage og hovedindgangen fremhævedes. Den oprindelige stationsbygning er indkorporeret i den nuværende. Syd for stationsbygningen opførtes et vandtårn, en to-sporet remise, der i dag er ombygget til kontor- og opholdslokaler.
Næstved station er efterhånden blevet udvidet og ombygget flere gange, men den mest gennemgribende omkalfatring fandt sted i årene 1918-24; omkostningerne løb op mod de 3 mill. kr. men man fik da også noget for pengene den gang. Alle de bestående ældre anlæg blev berørt af ombygningerne, alle niveauskæringer i og omkring Næstved blev erstattet af over- eller underføringer; nye perroner med perrontunnel blev anlagt. Der opførtes en lokomotivremise (rundremise med 8 spor) og den første del af 2. spor til Vordingborg blev taget i brug (Næstved-Lov 1923/24), og endelig tilkom indføringen af banen til Ringsted. Kun stationens hovedbygning lod man i fred, men dens tur kom i årene 1938-42, da den blev ombygget til ukendelighed.
Lokaltogene til Ringsted holdt til på spor II; på spor I havde Slagelsetogene hjemme, og det mellemliggende spor var maskinspor. Banen til Ringsted fulgte Slagelsebanen et stykke mod nord; da Ringstedsporet blev lagt, flyttedes Slagelsesporet to meter mod vest, hvorved dets stigningsforhold blev forbedrede. Hvor de to baner skiltes, skar Ringstedsporet militærsporet, der anlagdes efter Slagelsebanens åbning, således at der kunne føres tog direkte fra Køge mod Slagelse uden at skulle rebroussere i Næstved. Der blev ikke gjort meget ud af niveauskæringen med Ringstedsporet, idet der henlagdes et sporstykke, der i »påkommende tilfælde« hurtigt kunne indlægges. Denne ulejlighed kunne have været sparet, for det 1,63 km lange militærspor blev nedlagt allerede i 1925.
NPMB
På stationen i Næstved, lå Næstved-Præstø-Mernbanens spor længst væk fra stationsbygningen. På stedet er der endnu skinner, men man kan ikke længere bruge tunnelen under sporarealerne, hvis man vil ud til de fjerneste spor, da tunnelen er lukket af, hvor opgangene til de fjerneste statsbanespor er placeret. Ved at følge sporet mod Præstø, kommer man snart til broen, hvor banen var ført under Ringvejen i Næstved. Broen var gennem mange år dækket til, men blev i 1998 gravet frem igen, efter der blev anlagt en ny vej til centrum under denne bro, - præcis der, hvor banen lå. Turen fortsætter forbi Rønnebæksholm, på det som nu hedder Laugstien frem til Rønnebæk, hvor der i en del år lå et sidespor, beregnet til roekørsel.
