I begyndelsen af 1300-tallet lod kongen, antagelig Erik Menved, opføre en ny borg, Korsør Slot, ved indløbet til Noret formentlig for at have et opholdssted, når han ventede på overfart, og for at borgen kunne dække overfarten i krisetider.
I et dokument fra 1329 optræder stednavnet Corshu, som sandsynligvis er Korsør. Dette er den ældste bevarede kilde, hvor navnet Korsør optræder, og den forbindelse, det nævnes i, er Korsør Slot. I et brev fra 1341 nævnes helt tydeligt Korsør Slot. Der har måske stået et sømærke i form af et kors på en gruset strandbred (på gammeldansk ør) ved kysten for at vise de søfarende ind i Noret til Tårnborg. Dette korsformede sømærke og dets placering er muligvis baggrunden for stednavnet Korsør.
Der har sandsynligvis boet nogle få mennesker, der levede af fiskeri o.lign. i ly af slottet; men en by groede ikke naturligt frem. Efterhånden som kongens følge på rejser blev større, havde kongen brug for byer ved overfartsstederne, hvor hans folk og heste kunne indkvarteres. I begyndelsen af 1400-tallet gav Erik af Pommern (1396-1439) ordre til, at indbyggerne i Tårnborg, der helt havde udspillet sin rolle som handelsplads, skulle flytte og grundlægge en ny by ved Korsør Slot.
 1425 gav han byen købstadsprivilegier, hvorved den fik en række rettigheder i forhold til det omgivende land og i forhold til kongen. Endnu i 1441 tales om, at byen var under opbygning. Det var ikke handelscentret Tårnborg, der blev flyttet til Korsør. Korsør blev ingen stor handelsby i middelalderen. Muligvis havde det samkvemsmønster, som Tårnborgs blomstring hvilede på, ændret sig. Desuden lå Korsør dårligere oplandsmæssigt end Tårnborg. Kongens formål med at tildele byen privilegier var måske at sikre, at der var forsyninger på stedet til at dække de rejsendes behov.