De ældste spor af en bydannelse er fundet syd for Tårnborg Kirke ved Korsør Nor. Ved undersøgelser 1985‑87 blev der fundet rester af bindingsværkshuse, brolagte gader og fortove samt et righoldigt fundmateriale dateret fra vikingetiden og til ca. år 1400. Disse afspejler betydelige handels- og håndværksaktiviteter på stedet. De exceptionelt mange mønter fra perioden 1241‑1375 viser, at stedet fungerede som en regional handelsplads og indløsningssted for gamle mønter i forbindelse med de talrige pengeombytninger, der fandt sted på denne tid.
Korsør fik sine første købstadsprivilegier i 1425. Byen er antagelig vokset frem i anden halvdel af 1300-tallet, efter at den tidligere så livlige handelsplads ved Tårnborg sygnede hen. Korsør opstod i skyggen af Korsør Slot (Korsør Fæstning), hvis tårn formentlig er opført i årtierne omkring år 1300. Syd for slottet voksede en by efterhånden frem, og mellem Baggade og Algade blev der opført en kirke viet til Sankt Gertrud.
Fæstningen var ramme om vigtige politiske forhandlinger i bl.a. 1376 og 1438, hvilket kan tages som udtryk for, at Korsør allerede da var et af Danmarks vigtigste overfartssteder.
I senmiddelalderen og i 1500-tallet var fæstningen bolig for lensmanden i Sydvestsjælland. I 1605 flyttede han til Antvorskov, men Korsør fastholdt funktionen som opkrævningssted for skatter indtil 1863, og den lange magasinbygning fra 1609 blev brugt til oplagring af skattekorn. Korsør og Lilleø fik hvert sit voldanlæg i 1659. De blev anlagt af den svenske besættelsesmagt i forventning om, at Danmark for fremtiden ville være en del af Sverige.
Selv om Korsør kun havde et lille opland, og byen var i økonomisk krise ca. 1660‑1800, var den 1760‑95 hjemsted for to matadorer, Rasmus Langeland og Marcus Lauritzen, der engagerede sig i søfart på fjerne himmelstrøg. Rasmus Langeland købte det meste af fæstningen i 1764, men 11 år senere blev området igen overtaget af staten. Fæstningens militære funktion ophørte reelt i 1856. Korsørs indbyggertal lå i 1787 på 1.269.
Selv om færgefarten havde stor national betydning – især pga. behovet for at transportere post og soldater mellem landsdelene – blev der først omkring år 1800 taget seriøse skridt til en forbedring af Korsørs havn, som da kun bestod af to skibsbroer. Afgørende ændringer af havnens udseende begyndte dog først, da Egø, Lilleø og Magleø blev gjort landfaste med Halsskov i 1840’erne, den første bro mellem byen og Halsskov blev anlagt i 1847, og jernbanestationen blev indviet i 1856. Indtil 1845 havde Halsskov henligget som overdrev, men i 1850’erne blev der opført et jernstøberi, to teglværker og flere andre industrianlæg i den nye bydel. I samme årti flyttede den store skibsreder Jørgen Kruuse sit skibsværft dertil. Halsskov voksede især stærkt ca. 1880‑1914, hvor Korsørs rolle som vestsjællandsk handelsknudepunkt også blev forstærket. Det gjaldt bl.a. import af kul og eksport af kvæg og svin til Kiel med henblik på slagtning. Befolkningstallet, der havde været på 1.819 i 1850, nåede i 1916 op på 9.162.
Efter opførelsen af en ny banegård og nye færgelejer 1904‑06 og endnu en havneudvidelse 1910‑12 fulgte en mere rolig anlægsperiode, men i 1957 blev der etableret en ny færgeforbindelse, nemlig mellem Halsskov og Knudshoved. Tre år senere blev flådestationen indviet. I årene 1960‑65 etablerede tre store industrier, Hollesens Radiatorfabrik, C. Hjort & Co. og Basta, sig i Korsør, og i 1969 blev byens glasproduktion sat kraftigt i vejret, efter at Korsør Glasværk var blevet overtaget af Scanglaskoncernen. Alt dette stimulerede den økonomiske vækst i byen, og befolkningstallet voksede også. I 1970 blev der registreret 15.502 indbyggere.
Den økonomiske krise efter 1973 og lukningen af Hollesen (1974) og Scanglas (1982) førte til en betydelig arbejdsløshed, især blandt ufaglærte. Da ca. 1.500 korsoranere i 1990’erne var beskæftigede i jobs med tilknytning til færgefarten, frygtede mange, at byen ville blive kastet ud i endnu en alvorlig krise, når den faste forbindelse over Storebælt var blevet en realitet. Det skete dog ikke, takket være flådestationens kraftige ekspansion i 1990’erne, som betød, at den ved afslutningen af årtiet beskæftigede lige så mange, som der få år forinden havde arbejdet ved overfarten. Indbyggertallet i Korsør har ligget nogenlunde konstant i tiden efter 1970, og i 2006 var det 14.850.
