Marine food-reliant subsistence systems such as those in the African Middle Stone Age (MSA) were not thought to exist in Europe until the much later Mesolithic. Whether this apparent lag reflects taphonomic biases or behavioral distinctions between archaic and modern humans remains much debated. Figueira Brava cave, in the Arrabida range (Portugal), provides an exceptionally well preserved record of Neandertal coastal resource exploitation on a comparable scale to the MSA and dated to similar to 86 to 106 thousand years ago. The breadth of the subsistence base-pine nuts, marine invertebrates, fish, marine birds and mammals, tortoises, waterfowl, and hoofed game-exceeds that of regional early Holocene sites. Fisher-hunter-gatherer economies are not the preserve of anatomically modern people; by the Last Interglacial, they were in place across the Old World in the appropriate settings.