The first significant evidence of marine resource use among Europe's Neanderthals is detailed in a new report, demonstrating a level of marine adaptation previously only seen in their contemporary modern humans living in southern Africa. The results further close the behavioral gap once thought to separate modern humans from their closest evolutionary cousins. For modern humans, coastal adaptations are widely recognized as having roots in southern Africa and dating as far back as ~160 thousand years ago (kya). Whether Neanderthals shared a similar interest in the sea's cuisine is debated. Some suggest that the consumption of the seafood and the brain-boosting fatty acids seafood contains enhanced cognitive development in early modern humans, allowing for the wide variety of technological and cultural innovations that blossomed during the Middle Stone Age (MSA), a period spanning 200-25 kya. This in turn allowed our species to expand out of Africa and outcompete coeval hominins. Archaeological evidence of Neanderthal coastal adaptation, meanwhile, is virtually unknown. João Zilhão and colleagues report on recent excavations at the Figueira Brava site on Portugal's coast, which revealed a uniquely preserved record of intense, systematic and long-term coastal resource use by Neanderthals during the Last Interglacial. The seaside site was dated to roughly 106-86 kya and contained middens rich in marine and terrestrial food remains. According to Zilhão et al., Figueira Brava's occupants relied on the sea in a scale comparable to the modern humans of MSA Africa. The results suggest that fisher-hunter-gatherers were widespread and likely relied on the sea earlier than previously thought. The lack of supporting evidence on this to date, they say, is likely a result of Pleistocene sea level-rise, which inundated similar sites across coastal Europe. Manuel Will discusses the study further in a related Perspective.