På den strategisk gode placering ved et gammelt vadested mellem Inderfjord og Noret, hvor gennemløbet er smallest, blev Skælskør anlagt kort før år 1200.
De ældste spor af bydannelsen er fundet på gennemløbets vestside, hvor Sankt Nicolai Kirke blev opført i begyndelsen af 1200-tallet. Nord for kirken er der også fundet bebyggelsesspor fra 1200-tallet. Ifølge de skriftlige kilder blev der opført en borg i 1200-tallet, som blev befæstet med Helledegrøften. Grøftens østlige del, en 4 m bred og 1,3 m dyb grøft ved Lovsøvej mod vest, er undersøgt, dog er der hverken fundet spor af selve borgen eller den vestlige del af Helledegrøften.
Byens middelalderlige gadeplan bestod af Vestergade, Gammeltorv og Skovvej i vest og Algade i øst. Syd for Algade er der også fundet spor af middelalderbebyggelse samt af en afgrænsning af byen i form af en mindre grøft. Bydannelsens havn lå ligeledes på gennemløbets sydlige bred.
Det ældst kendte købstadsprivilegium for Skælskør er fra 1414. Byen menes at have været et vigtigt overfartssted mellem Sjælland og Fyn i 1200‑1300-tallet. Den spillede også en stor rolle under stridighederne om den danske trone i 1250’erne, og det nu forsvundne voldanlæg vest for byen blev muligvis etableret i denne forbindelse. Omkring år 1300 dannede Skælskør flere gange ramme om vigtige politiske møder, men siden har byen stået i skyggen af Korsør. Byens karmeliterkloster blev oprettet i 1418 og nedlagt i 1532.
Fra senmiddelalderen stammer Skælskørs gamle latinskole, der ligger på Gammelgade 4. Den er oprindelig opført ca. 1525 som kirkelade til Sankt Nicolai Kirke, der ligger ved siden af.
Skælskør fik et knæk under svenskekrigene 1658‑60 og den efterfølgende lange købstadskrise, og flere vestlige gader blev pløjet op sidst i 1600-tallet. Indbyggertallet lå i 1787 på 501. Skælskør oplevede først rigtig fremgang omkring år 1800, hvor der bl.a. blev gravet en rende gennem fjorden, hvorefter skibene kunne sejle ind til byen i stedet for som hidtil at kaste anker på Storebælt, så al søværts varetransport til og fra byen måtte foregå med pramme.
Skælskør har i høj grad delt opland med Korsør og Slagelse, men nogenlunde haft Stigsnæs og de nærmeste landsbyer mod øst for sig selv, og handelslivet har derfor, i alt fald siden 1700-tallet, for det meste fundet sted i den østlige bydel. Landsbyen Smidstrup, der hørte til herregården Borreby, blokerede for en udvidelse af Skælskør mod øst indtil 1806, hvor den brændte. Derefter blev grundene mageskiftet til Skælskør, og Nytorv anlagt på dette sted. Skælskørs overdrev blev omdannet til agerjord efter udskiftninger i hhv. 1585, 1646 og 1795, hvor der blev knyttet mange jordlodder til de enkelte ejendomme. Agerbruget var dog kun et bierhverv for de fleste borgere.
I 1850 lå indbyggertallet på 1.134, og dette var i 1901 vokset til 2.501. En markant fremgang for landbruget efter ca. 1830 banede vejen for økonomisk vækst i Skælskør, hvor slægterne Harboe og Lotz prægede udviklingen med et stort engagement i handel, industri og rederivirksomhed. På højdepunktet for Skælskørs skibsfart i 1891 hørte 23 sejlskibe med en samlet tonnage på 6.337 registertons hjemme i byen, og der sejlede da Skælskørskibe på flere verdensdele. Havnen blev udvidet 1856‑58 og igen i 1893 i forbindelse med etableringen af jernbaneforbindelsen til Dalmose året før. Dampmøllen blev opført i 1853. Andre vigtige industrier var jernstøberiet og maskinfabrikken i 1881, bryggeriet Harboe og Lotz (nu: Harboes Bryggeri A/S) i 1883 og svineslagteriet i 1896. Skælskør Frugtplantage blev grundlagt i 1898. Omkring år 1900 fik Skælskør også en række nye offentlige bygninger, bl.a. et råd-, ting- og arresthus (1895‑96) som afløser for det hidtidige rådhus, en toldkammerbygning (1886) og flere skoler.
Byen fik kun få nye industrier af betydning mellem 1920 og 1970. Derimod opstod der flere nye institutioner, bl.a. et gigtsanatorium (1932‑33) og et julemærkehjem (1962). Persontransporten på jernbanen ophørte i 1950. Skælskør oplevede kun en beskeden befolkningsvækst fra 1920 til 1960, men i de følgende ti år voksede indbyggertallet fra 3.241 til 4.585 i 1970, hvad der bl.a. afspejler de nye beskæftigelsesmuligheder i området efter anlæggelsen af Stigsnæsværkerne: Gulf-raffinaderiet i 1963 og SEAS’ kraftværk i 1966. I 1966 blev Skælskør administrativt center i en ny kommune af samme navn.
Befolkningsvæksten fortsatte efter 1970, og i 2006 havde byen 6.373 indbyggere. I denne periode havde bryggeriet stor vækst, og Bähncke A/S henlagde i 1989 produktionen af konserves mv. til Skælskør. Byen var også hjemsted for en folkehøjskole (1973‑2005) og for det internationalt kendte keramiske center Guldagergaard (etableret 1998). Desuden var turismesektoren i stor vækst.
