Shell middens, or shell-matrix deposits, occur in large numbers across the coastlines of the world from the mid-Holocene (ca. 6000–5000 cal BC) onwards, often forming substantial mounds. However, they become smaller, rarer or absent as one goes back into earlier periods, suggesting a world-wide process of economic intensification. Since sea level was generally much lower during these earlier periods, a critical question is the extent to which mounded shell middens could have accumulated on now-submerged palaeoshorelines, and if so, how they were affected by the potentially destructive impact of sea-level rise. Further, and important to modern practice, it is essential that archaeologists consider how such sites can be discovered through underwater investigation. Here we offer a proof of concept that shell middens can survive submergence and can be detected, using systematic investigation of a rare example of a confirmed underwater shell midden at the Mesolithic site of Hjarnø (ca. 5300–4300 cal BC) in Denmark. We compare the excavation results with the results of geophysical survey, explore the problems of distinguishing underwater cultural shell middens from natural shell beds and conclude that shell middens can survive inundation by sea-level rise and can be detected by remote sensing, but require at least minimally invasive sampling to establish their cultural status. We suggest the methods developed may be applicable to coastal and marine sites impacted by postglacial sea-level rise worldwide.