Research on global ice-volume changes during Pleistocene glacial cycles is hindered by a lack of detailed sea-level records for time intervals older than the last interglacial. Here we present the first robustly dated, continuous and highly resolved records of Red Sea sea level and rates of sea-level change over the last 500,000 years, based on tight synchronization to an Asian monsoon record. We observe maximum 'natural' (pre-anthropogenic forcing) sea-level rise rates below 2 m per century following periods with up to twice present-day ice volumes, and substantially higher rise rates for greater ice volumes. We also find that maximum sea-level rise rates were attained within 2 kyr of the onset of deglaciations, for 85% of such events. Finally, multivariate regressions of orbital parameters, sea-level and monsoon records suggest that major meltwater pulses account for millennial-scale variability and insolation-lagged responses in Asian monsoon records.