A detailed record of sea surface temperature from sediments of the Cape Basin in the subtropical South Atlantic indicates a previously undocumented progression of marine climate change between 41 and 18 thousand years before the present (ky B.P.), during the last glacial period. Whereas marine records typically indicate a long-term cooling into the Last Glacial Maximum (around 21 ky B.P.) consistent with gradually increasing global ice volume, the Cape Basin record documents an interval of substantial temperate ocean warming from 41 to 25 ky B.P. The pattern is similar to that expected in response to changes in insolation owing to variations in Earth's tilt.