The antiquity and nature of coastal resource procurement is central to understanding human evolution and adaptations to complex environments. It has become increasingly apparent in global archaeological studies that the timing, characteristics, and trajectories of coastal resource use are highly variable. Within Africa, discussions of these issues have largely been based on the archaeological record from the south and northeast of the continent, with little evidence from eastern coastal areas leaving significant spatial and temporal gaps in our knowledge. Here, we present data from Panga ya Saidi, a limestone cave complex located 15 km from the modern Kenyan coast, which represents the first long-term sequence of coastal engagement from eastern Africa. Rather than attempting to distinguish between coastal resource use and coastal adaptations, we focus on coastal engagement as a means of characterising human relationships with marine environments and resources from this inland location. We use aquatic mollusc data spanning the past 67,000 years to document shifts in the acquisition, transportation, and discard of these materials, to better understand long-term trends in coastal engagement. Our results show pulses of coastal engagement beginning with low-intensity symbolism, and culminating in the consistent low-level transport of marine and freshwater food resources, emphasising a diverse relationship through time. Panga ya Saidi has the oldest stratified evidence of marine engagement in eastern Africa, and is the only site in Africa which documents coastal resources from the Late Pleistocene through the Holocene, highlighting the potential archaeological importance of peri-coastal sites to debates about marine resource relationships.