Korsør Fæstning blev anlagt i 1300 tallet af Valdemar Atterdag som afløser for Tårnborg. Dog stammer dele af fæstningstårnet tilbage fra 1100 tallet. Tårnborg havde Valdemar generhvervet fra grev Johan af Holsten i 1344. I 1534 overgav fæstningens kommandant, Knud Rud, borgen til grev Christoffer af Oldenburg, som sammen med lybeckerne kæmpede for Christian den 2‘s løsladelse fra Sønderborg Slot og genindsættelse som konge. Christian 4 byggede Magasinbygningen i 1609. Slottets fæstningsværer blev udbygget af svenskerne under Karl-Gustav krigene 1657-1160.
