Bydannelsen voksede frem på et plateau på Susås nordside, der skrånede mod vest og syd. De ældste spor af aktivitet på stedet er fundet i området ved Helligåndshuset og består af plovfurer og østersøkeramik fra 1000- eller 1100-tallet. Denne bydannelse synes at have haft sin oprindelse i en bebyggelse af uvis karakter fra ældre germansk jernalder (ca. 375-ca. 550). I vikingetiden (ca. 800‑1050) lå der formentlig en art handelsplads på stedet, som udgjorde grundlaget for den senere bydannelse. Fjorden udgjorde en god naturhavn og gav beskyttelse mod fx vendernes angreb. Byen var allerede fra tidlig middelalder præget af både kongers, stormænds, kirkers og klostres interesser.
I 1100-tallet havde byen både en sognekirke og en vandmølle, og Næstved blev udvidet ved landindvinding i Suså. Ved hjælp af hegn og jord blev Suså gjort smallere og den indvundne jord bebygget.
I samme periode blev byens nordlige afgrænsning formentlig også udvidet, idet undersøgelser i bl.a. Farvergade og Vinhusgade viser, at spor af agerbrug på denne tid blev afløst af bebyggelse.
I 1135 blev Næstved nævnt i en skriftlig kilde for første gang, da Bodilslægten skænkede Sankt Peders Kirke og en række ejendomme i byen til oprettelse af et nyt klostersamfund af benediktinerordenen, det senere Skovkloster. I 1140 skænkede kong Erik Lam Næstveds torverettigheder til det nye kloster, og det var, sammen med en række andre privilegier, med til at gøre Skovklosteret til en magtfuld institution i byen. Foruden de to bykirker Sankt Peders og Sankt Mortens kom der i 1200-tallet både et sortebrødrekloster og et gråbrødrekloster til (hhv. i ca. 1242 og 1265). Syd for byen i Åderup opførtes en Sankt Jørgensgård med kirke. Siden slutningen af 1300-tallet havde Helligåndshuset i Ringstedgade taget sig af forældreløse børn, syge, gamle og fattige. Næstved var den eneste by ud over stiftsbyerne med så stort et antal kirke- og klosterinstitutioner, og de kom til at præge byens udvikling i hele perioden. Fra slutningen af 1100- og 1200-tallet blev store områder byggemodnet, og der er fundet spor af specialiseret håndværk, heriblandt smedning og kammageri.
Den omfattende handel med de hanseatiske byer langs Østersøens sydkyst i høj- og senmiddelalderen var af vital betydning. Næstved lå perfekt for hansestæderne, hvis købmænd havde brug for en indfaldsport til Sjælland samt et centralt sted for opkøb af sjællandsk korn og fisk. Der blev i perioden også slået mønt i Næstved.
Den ældste købstad lå formentlig omkring Sankt Peders Kirke nær havnen. Gadenettet i den historiske bykerne stammer i al væsentlighed fra middelalderen, og navne som fx Kindhestegade har overlevet frem til i dag. I løbet af høj- og senmiddelalderen bredte bebyggelsen sig til et større område mod nord, afgrænset af Sandbjerget. Suså delte endvidere Næstved i to bydele i høj- og senmiddelalderen, en østlig Store Næstved og en vestlig Lille Næstved. Flere broer omtalt siden 1405 bandt byen sammen, men ca. år 1500 skete en opsplitning mellem bydelene, hvorefter Store Næstved blev købstad, mens Lille Næstved svandt ind til en landsby. Næstved havde også flere byporte, men ingen kendt bybefæstning. I byens sydlige kant lå borgen Husvolden, der formentlig blev opført i 1200-tallet, og hvorfra holstenerne kontrollerede Næstved i en tid i 1300-tallet, indtil kong Valdemar Atterdag i 1345 indtog borgen. Borganlægget er hidtil ikke arkæologisk undersøgt.
Rige købmænd byggede huse og gårde, og der blev opført et nyt rådhus i midten af 1400-tallet. Gennem det meste af middelalderen var Næstved underlagt Skovklosterets magt, men fra slutningen af 1400-tallet skiftede magtbalancen til fordel for konge, borgere og rådmænd.
Reformationen i 1536 fik stor betydning for Næstved. Gråbrødrekloster blev nedlagt i 1532, hvorefter nedrivningen begyndte, og området blev udlagt til torv. Kun kirken stod tilbage indtil 1553. Dele af sortebrødreklosteret blev revet ned i midten af 1500-tallet, og resten omdannedes til herregård.
Med de katolske institutioners nedlæggelse blev omsorgen for syge og fattige en borgerlig opgave. Næstved fik overdraget Helligåndshuset i 1532, og spedalskhedshospitalet indgik heri efter Reformationen. I 1817 opførte Præstø Amt et amtssygehus i Ringstedgade med 24 sengepladser.
1600- og 1700-tallet var præget af nedgangstider. Den blomstrende handel aftog, fordi større skibe var nødsagede til at losse og laste i pramme ved ladepladsen i Karrebæksminde for herefter at stage prammene gennem fjorden og op ad åen til Næstved. De ringe vilkår for handelen, følger fra svenskekrigene og epidemier betød, at byen forarmedes. De dårlige tider medførte, at flere boliger blev revet ned eller fik fjernet første sal, og byen havde ingen problemer med at være inden for middelalderbyens rammer. Siden 1684 var Næstved garnisonsby, og til det formål blev Grønnegades Kaserne opført i 1799 på Sandbjerget.
Først i løbet af 1800-tallet begyndte det at lysne. I 1812 blev Den Danneskioldske Kanal indviet, så bl.a. tømmer fra skovene på Midtsjælland kunne fragtes til Næstved og videre til udskibning i Karrebæksminde. Havneforholdene blev forbedret, og i 1856 hørte 20 fartøjer hjemme i Næstved. Økonomisk fremgang og gode landbrugskonjunkturer satte skub i udviklingen, og købmænd dominerede byen med kornhandel, skibsfart og opførelse af pakhuse. De gunstige forhold smittede af på befolkningstallet, der steg fra 1.501 i 1787 til 2.644 i 1845.
I 1850 havde Næstved stort set den afgrænsning, som byen havde haft siden middelalderen, men byportene blev revet ned i 1851, og vejen var dermed banet for en åbning af købstadens grænser. Da jernbanen Roskilde-Køge-Næstved-Masnedsund kom til byen i 1870, blev stationen lagt uden for byen, og det var nødvendigt at grave en vej igennem Sandbjerget hertil. Byens snirklede gadenet og facadelinjer blev tilrettet af Bygningskommissionen i 1877 for at gøre gadebilledet mere sammenhængende og ensrettet og dermed skabe rammer for fremtidige byggeprojekter og udvidelser. Med til byens modernisering hørte også opførelse af gasværk i 1862, vandværk i 1888 og elværk i 1909.
Industrialiseringen brød igennem fra 1870’erne, og vandringen fra land til by fik indbyggertallet til at vokse betydeligt. I 1855 var byens indbyggertal 3.228, i 1916 var der sket mere end en tredobling til 11.288 indbyggere. Omkring år 1900 bredte boligbyggeriet sig til de gamle bymarker, hvor Brandtsgadekvarteret, der rummede mindre fabrikker og boliger til arbejdere, blev opført fra omkring 1890. Som følge af urbaniseringen blev der i begyndelsen af 1900-tallet mangel på mindre lejligheder, og der opførtes i perioden 1918‑32 kommunalt boligbyggeri i byens udkanter ved Gallemarken, Kastanievejskvarteret, Skyttemarksvej og Vordingborgvej.
Der opstod behov for at regulere forholdene for samfundets udsatte. Næstved fik ny fattiggård i 1883 uden for byen og husede fra 1867 desuden Tvangsarbejdsanstalten for Præstø Amt. Der opførtes plejehjem i 1916. Desuden blev skolevæsenet forbedret, idet der opførtes to nye kommuneskoler i hhv. 1881 og 1912, og realskolen blev udvidet og fik i 1901 også adgang for piger.
Flere store virksomheder blev grundlagt. Den største var Maglemølle Papirfabrik, der i 1920 havde omkring 700 beskæftigede. Derudover var der De forenede Jernstøberier, Carl Paulsen – Jernstøberi & Maskinfabrik, Kählers keramikfabrik, tjærefabrikken Luxol, Trævarefabrikken Dan, Bryggeriet Fønix og A/S J.D. Koopmanns Svineslagteri. Kasernen i Grønnegade fik flere udvidelser, og det voksende militære mandskab, med 4. Dragonregiment som det dominerende, blev også indkvarteret hos private og i private kaserner. Statskasernen på Farimagsvej blev opført 1913‑14 som militær administrations- og depotbygning. I 1856 stod et nyt råd-, ting- og arresthus klar til brug på Hjultorv.
Næstveds udvikling til industriby tog for alvor fart efter 1. Verdenskrig, og især to markante begivenheder kom til at præge byen i 1930’erne. I 1935 fejrede den sit 800-års købstadsjubilæum med en udstilling, der rakte langt ud over byens grænser og varede i fire uger. Der blev opbygget en hel udstillingsby, som opførtes på de arealer, der var øremærkede til den anden store begivenhed, nemlig gravning af en kanal og anlæggelse af en helt ny havn. I 1938 blev den nye havn indviet, samtidig med at De Forenede Papirfabrikker kunne tage en ny papirfabrik i brug ved havnen. Næstveds placering ved Suså havde været gunstig for byen, men den langsomme og besværlige omladning af skibslaster i Karrebæksminde kunne slet ikke følge med kravene fra den stigende industrialisering. Havnens største kunde var papirfabrikken, og råvarer til fabriksanlægget måtte prammes yderligere gennem Storebro. Kanal- og havneprojektet kom derfor også til at omfatte en rørlægning af Suså langs Havnegade, anlæggelse af en ny vej ovenpå og jernbanespor ud til havneområdet. Forbedring af søvejen til Næstved foregik i et samarbejde mellem private og offentlige interesser.
På trods af mellemkrigstidens økonomiske kriser fortsatte byggeprojekterne med nyt kasernebyggeri til Gardehusarregimentet på Ridemarken i byens østlige udkant (1940), opførelse af et nyt rådhus og brandstation (1940), mødre- og svangrehjem (1942) samt to skoler (1942) ved de nye boligområder i Lindebjergområdet og Markkvarteret. Boligkomplekser skød op langs indfaldsvejene, og som grønne områder i byen etableredes haveforeningerne Ellevang (1935) og Ellebækshøj (1948).
I 1921 havde Næstved 12.189 indbyggere, og i 1965 var tallet nået op på 31.008. Industribyen fortsatte med at udvikle sig op gennem 1950’erne og 1960’erne med ny infrastruktur, byggeri af almene og private boliger, plejeboliger og et nyt 14-etagers sygehus. Mange af de gamle købmandsgårde og bygninger omkring Axeltorv måtte vige for moderniseringen, og husene i Bredstræderne blev revet ned for at give plads til et parkeringsanlæg i to etager. Et helt nyt kvarter, Sct. Jørgens Park, voksede frem sammen med nye skoler, daginstitutioner og supermarkeder.
Efter 1970 fortsatte Næstved med at udvikle sig på alle sider af det gamle centrum og indledte en transformation fra industrisamfund til et samfund domineret af handel og service. Foruden mindre virksomheder lukkede papirfabrikkerne i hhv. 1971 og 1992, og byen mistede mange arbejdspladser. Også Næstveds tid som garnisonsby var endegyldigt forbi i 2001, da Gardehusarregimentet flyttede til Slagelse. Byen udvidede sig mod vest med boligbyggeri og mod nord med Næstved Storcenter (1989) og Megacenter (1990). Omkring centrene opstod et nyt erhvervsområde med butikker og let industri, og centrene var med til at styrke Næstveds regionale status som handelscenter.
Trods nybyggeri blev det også prioriteret at bevare ældre bygningsværker, fx Kompagnihuset og Grønnegades Kaserne. Til gengæld måtte de gamle forsyningsanlæg til gas og el og badeanstalten ved Suså rives ned for at give plads til grønne områder, da åen igen i år 2000 blev fritlagt langs Havnegade til udløb i havnen. Indbyggertallet steg fra 35.695 i 1970 til 41.158 i 2006.
