Genetic and anatomical evidence suggests that Homo sapiens arose in Africa between 200 and 100 thousand years (kyr) ago, and recent evidence indicates symbolic behaviour may have appeared approximately 135-75 kyr ago. From 195-130 kyr ago, the world was in a fluctuating but predominantly glacial stage (marine isotope stage MIS6); much of Africa was cooler and drier, and dated archaeological sites are rare. Here we show that by approximately 164 kyr ago (+/-12 kyr) at Pinnacle Point (on the south coast of South Africa) humans expanded their diet to include marine resources, perhaps as a response to these harsh environmental conditions. The earliest previous evidence for human use of marine resources and coastal habitats was dated to approximately 125 kyr ago. Coincident with this diet and habitat expansion is an early use and modification of pigment, probably for symbolic behaviour, as well as the production of bladelet stone tool technology, previously dated to post-70 kyr ago. Shellfish may have been crucial to the survival of these early humans as they expanded their home ranges to include coastlines and followed the shifting position of the coast when sea level fluctuated over the length of MIS6.