Since the 1990s the Mekong River delta has suffered a large decline in sediment supply causing coastal erosion, following catchment disturbance through hydropower dam construction and sand extraction. However, our new geological reconstruction of 2500-years of delta shoreline changes show that serious coastal erosion actually started much earlier. Data shows the sandy coast bounding river mouths accreted consistently at a rate of +2 to +4 km2/year. In contrast, we identified a variable accretion rate of the muddy deltaic protrusion at Camau; it was < +1 km2/year before 1400 years ago but increased drastically around 600 years ago, forming the entire Camau Peninsula. This high level of mud supply had sharply declined by the early 20th century after a vast canal network was built on the delta. Since then the Peninsula has been eroding, promoted by the conjunction of mud sequestration in the delta plain driven by expansion of rice cultivation, and hysteresis of long-term muddy sedimentation that left the protrusion exposed to wave erosion. Natural mitigation would require substantial increases in sediment supply well above the pre-1990s levels.