Kong Valdemar den Store byggede en borg omkring 1160 på stedet for den senere by. Sankt Andreas Kirke nær borgen blev opført i anden halvdel af 1100-tallet; den blev fundet af arkæologer i slutningen af 1800-tallet og er blevet udgravet flere gange. Omkring år 1200 blev den første teglstensborg bygget, og det var her, Jyske Lov blev givet i 1241 under kong Valdemar Sejr, der også afholdt danehof i byen. Kong Valdemar Atterdag udbyggede i 1360’erne borgen til Danmarks største kongeborg og etablerede en bybefæstning med volde, grave og formentlig også et mølleanlæg. Opstemning af vand bevirkede, at både byen og borgen blev omkranset af vand. Derfor fremstod Vordingborg som to øer.
Byens ældst kendte købstadsrettigheder er dokumenteret fra 1415, men Vordingborg fik formentlig sine første privilegier i 1200-tallet. Et dominikanerkloster antages at være blevet stiftet i Vordingborg i 1253, men blev nedlagt efter kort tid. Vor Frue Kirke blev muligvis grundlagt i anden halvdel af 1300-tallet. Byen har derudover haft Sankt Jørgensgård og et helligåndshus, der er nævnt i skriftlige kilder i 1466. Fra Vordingborg var der færgefart til Falster.
Uden for borgområdet er der fundet en stensat kælder fra før 1300-tallet. Kælderen har formodentlig hørt til et stenhus, der lå i Baisstræde, middelalderens eneste sidegade. På baggrund af østersøkeramik kan kælderen dateres til 1200-tallet, og lergulve fundet ved udgravningen vidner om, at bygningen har fungeret frem til 1600-tallet. Tæt ved kælderen er der fundet en grøft, der tolkes som den første bygrænse, anlagt omkring år 1200. I slutningen af 1300-tallet blev Algadeskatten nedgravet. Den bestod af 381 mønter gemt i en stentøjskande.
Svenskekrigene gik hårdt ud over byen og borgen. I 1673 blev Prins Jørgens Palæ opført på borgterrænet, men det blev sammen med dele af middelalderborgen nedrevet midt i 1700-tallet. I 1700-tallet blev Vordingborg Kirkeskov hærget af en række bybrande. 1717‑19 blev Vordingborg Rytterdistrikt oprettet, og Vordingborg blev da garnisonsby. Rytterdistriktet opløstes i 1774, og af området opstod bl.a. godserne Rosenfeldt, Iselingen og siden Marienlyst. Indbyggertallet lå i 1787 på 960. Midt i 1800-tallet blev den nordvestlige del af voldgraven fyldt op, og Slotstorvet skabt. Her blev byens tredje rådhus bygget 1843‑45.
I 1870 kom jernbanen – Den Sjællandske Sydbane – til Vordingborg med stationer både i Aarsleffsgade og i Masnedsund, hvor en helt ny bydel begyndte at vokse frem. I 1884 blev Masnedsundbroen indviet, og færgefarten til Falster blev flyttet til øens sydspids. Kalvehavebanen kom til i 1897.
Boulevardkvarteret opstod i forbindelse med etableringen af kasernen 1912‑13, hvor der også blev etableret sygehus. Sindssygehospitalet på Oringe blev bygget i 1858, hvilket medførte, at der blev opført gasværk i 1866, og dermed kom der gadebelysning i byen. 1909‑10 fik byen eget vandværk og hurtigt derefter elværk. I sidste halvdel af 1800-tallet opstod virksomheder som garveri, jernstøberi, tømmerhandel og andelssvineslagteriet (1889) i Masnedsund.
Sidst i 1800-tallet fik byen handelsskole, teknisk skole, seminarium og siden husmoderskole. Vordingborg oplevede en betydelig befolkningsvækst i anden halvdel af 1800-tallet. I 1855 lå indbyggertallet på 1.763, og dette tal var mere end fordoblet til 3.643 indbyggere i 1901. Indbyggertallet fortsatte med at stige i første halvdel af 1900-tallet, fra 7.273 i 1921 til 11.231 i 1950. Den moderne handelsby voksede frem langs Algade, og der blev bygget mange enfamilieshuse og lidt etagebyggeri.
Byen fik gymnasium i 1935, svømmehal i 1947 og sportshal i 1951. I 1937 blev den nye Masnedsundbro, Storstrømsbroen og byens nye station indviet. I 1940 blev kraft-varme-værket Masnedøværket opført, hvilket fik betydning for byens erhvervsliv. Plastfabrikken Nordisk Kamfabrik, siden Panther Plast A/S, blev grundlagt i 1933, og i 1946 kom ostefabrikken Buko og salatfabrikken Mayo til byen. Engelbredts skofabrik flyttede til Ørslev i 1961 som Jaco-sko og fik stor succes med Jacoform-skoene. I 1963 blev Vordingborg Køkkenet A/S grundlagt.
I 1965 toppede indbyggertallet med 11.905, derefter faldt det markant til 8.593 i 1990, men siden oplevede det en svag stigning, og i 2006 lå det på 8.923. I 1971 blev der udstykket et stort parcelhusområde fra godset Iselingen. Iselingeskolen blev bygget i 1975, og Vordingborg Uddannelsescenter i 1980. Andelssvineslagteriet stoppede med slagtninger i 1986. På Masnedø opstod Danmarks største tomatgartneri i 1988.
I 1991 startede TV2 Øst med station i Vordingborg. Industrihavnen blev flyttet fra Sydhavnen til Masnedø, hvorefter der blev bygget boliger i det gamle havneområde, og i 2006 åbnede kulturhuset Kulturarkaden.
