Few palaeoclimate archives beyond the polar regions preserve continuous and datable palaeotemperature proxy time series over multiple glacial-interglacial cycles. This hampers efforts to develop a more coherent picture of global patterns of past temperatures. Here we show that Mg concentrations in a subaqueous speleothem from an Italian cave track regional sea-surface temperatures over the last 350,000 years. The Mg shows higher values during warm climate intervals and converse patterns during cold climate stages. In contrast to previous studies, this implicates temperature, not rainfall, as the principal driver of Mg variability. The depositional setting of the speleothem gives rise to Mg partition coefficients that are more temperature dependent than other calcites, enabling the effect of temperature change on Mg partitioning to greatly exceed the effects of changes in source-water Mg/Ca. Subaqueous speleothems from similar deep-cave environments should be capable of providing palaeotemperature information over multiple glacial-interglacial cycles.