Sea-level rise is a global problem, yet to forecast future changes, we must understand how and why relative sea level (RSL) varied in the past, on local to global scales. In East and Southeast Asia, details of Holocene RSL are poorly understood. Here we present two independent high-resolution RSL proxy records from Belitung Island on the Sunda Shelf. These records capture spatial variations in glacial isostatic adjustment and paleotidal range, yet both reveal a RSL history between 6850 and 6500 cal years BP that includes two 0.6 m fluctuations, with rates of RSL change reaching 13±4 mm per year (2σ). Observations along the south coast of China, although of a lower resolution, reveal fluctuations similar in amplitude and timing to those on the Sunda Shelf. The consistency of the Southeast Asian records, from sites 2,600 km apart, suggests that the records reflect regional changes in RSL that are unprecedented in modern times.