Kirken var indviet til de rejsendes værnehelgen Skt. Gertrud. Dette taler også for teorien om Korsør som overfartsby. Selv om den tidligst blev opført i senromansk eller tidlig gotisk tid - formentlig samtidig med slottet - var den en af byens ældste bygninger. Den var oprindelig uden tårn. Et sådant blev bygget til formentlig omkring 1442. Kirkerummet var godt 7 m bredt og godt 22 m langt. Valdemar Atterdag (1340-75) fik i 1361 pavelig tilladelse til at indrette et kapel på slottet, formentlig for at gudstjeneste kunne afholdes her for slottets beboere og kongen, når han var i Korsør.