Vast amounts of fish bone lie preserved in Denmark's soil as remains of prehistoric fishing. Fishing was particularly important during the Atlantic period (ca. 7000-3900 bc, i.e. part of the Mesolithic Stone Age). At this time, sea temperature and salinity were higher in waters around Denmark than today. Analyses of more than 100,000 fish bones from various settlements from this period document which fish species were common in coastal Danish waters at this time. This study provides a basis for comparing the fish fauna in the warm Stone Age sea with the tendencies seen and predicted today as a result of rising sea temperatures. One example concerns the anchovy (Engraulis encrasicolus), which lived in the Stone Age sea, and has become more numerous in Danish waters since the mid-1990s. Other warm water fishes represented among the Stone Age bone samples include smoothhound (Mustelus sp.), common stingray (Dasyatis pastinaca), European sea bass (Dicentrarchus labrax), black sea bream (Spondyliosoma cantharus) and swordfish (Xiphias gladius). Surprisingly, Atlantic cod (Gadus morhua), whose biomass in the Kattegat and eastern Baltic Sea is presently at record low levels, was one of the most frequently caught species in the Danish Stone Age sea. These results demonstrate that major changes to the fish fauna near Denmark will occur as climate changes. However, exploitable cod populations can potentially be maintained in waters near Denmark, including the North Sea, but the vulnerability to climate change and the risk of stock collapse will increase at present high fishing mortalities.