The lowering of global sea level during the Pleistocene by more than 100 m and subsequent inundation of coastal areas constitutes a problem in terms of general research on early maritime-oriented societies. However, post-glacial isostatic rise in glaciated regions has produced raised shorelines of Late Pleistocene/Early Holocene age, e.g., in Scandinavia, Patagonia, and North America. As these regions contain the oldest preserved coastal areas, they are imperative for the understanding of the development of maritime hunter-gatherers. The extensive Norwegian coastline appears to have been colonized in the course of the few hundred years around 9500 cal B.C. An overwhelming majority of Early Holocene sites are found in the fiord/skerry coastal landscape, indicating that marine resources were vital in the subsistence pattern of people occupying the region. The lithic tradition is clearly linked to specialized megafauna hunters in the continental plains (the Ahrensburgian complex of northwestern Europe), but the facts about and dynamics of the development of the marine subsistence pattern are unclear. This paper focuses on this problem—with comparative perspectives towards the emergence of maritime foragers in Patagonia.