De første årtusinder steg landet hurtigere end vandet, og Danmark blev en del af et stort fastland. Jylland og øerne udgjorde et samlet område, der var landfast med Sydsverige og England, og Storebælt var et landområde med søer og floder. Jorden var dækket af arktisk tundra med rypelyng, pil, birk og græs. Rensdyrflokke vandrede over landet, og de første stenalderjægere kom hertil. Deres vigtigste bytte var rensdyrene. Jægerne levede som nomader, og der var meget få af dem.
Omkring 9500 f. Kr. blev det varmere, og landet begyndte at blive dækket med skov. Med varmen forsvandt rensdyrene, og jagten rettede sig nu fortrinsvis mod store dyr som elg og urokse. Landhævningen gik langsommere, mens havstigningen fortsatte, og det medførte, at et søsystem, der havde dannet sig i Storebælt, fik forbindelse til havet op mod år 7000 f. Kr. Kystlinjen lå da ca. 3 km vest for Halsskov og Musholm, og Sprogø var ca. 5 km lang fra øst til vest.
Klimaet, der havde været tørt og køligt, blev nu fugtigt og varmt, varmere end i dag, og den åbne skov med fyr og birk ændredes til en tæt urskov af hassel, elm, lind, el og eg, der efterhånden dækkede landet. Det store vildt fik dermed dårligere levemuligheder; men til gengæld gav varmen et rigt liv i havet, som nu blev grundlaget for meneskenes eksistens.
Befolkningen fra de første årtusinder efter istiden har kun sat sig få spor omkring Korsør. En pilespids fra ca. 11000 f. Kr., der er fundet på Halsskov, vidner snarere om en jagtekspedition ind i landet end om beboelse. Det er karakteristisk for jægerstenalderen (13000-3900 f. Kr.), at bopladserne lå ved kysten eller ved åer og søer. De bopladser, jægerbefolkningen må have haft her i området, ligger derfor nu langt ude i Storebælt.
Efter ca. 7000 f. Kr. satte en kraftig havstigning ind, der opdelte Danmark i mindre øer. Omkring 6000 f. Kr. fik Storebælt nogenlunde sin nuværende udstrækning. På dette tidspunkt brød vandet ind i Korsør Nor, der hidtil havde været en dal, og på Halsskov blev der dannet en fjord i de nuværende lavtliggende områder. De næste 2-3000 år steg vandet stadig, indtil det nåede sin største udbredelse ca. 3500 f. Kr. Siden da har landet hævet sig en meter ved Korsør; men i det væsentligste var den kystlinje nu skabt, som først blev ændret, da der blev foretaget store landvindinger i 1800-tallet.