Ice volume (and hence sea level) and deep-sea temperature are key measures of global climate change. Sea level has been documented using several independent methods over the past 0.5 million years (Myr). Older periods, however, lack such independent validation; all existing records are related to deep-sea oxygen isotope (delta O-18) data that are influenced by processes unrelated to sea level. For deep-sea temperature, only one continuous high-resolution (Mg/Ca-based) record exists, with related sea-level estimates, spanning the past 1.5 Myr. Here we present a novel sea-level reconstruction, with associated estimates of deep-sea temperature, which independently validates the previous 0-1.5 Myr reconstruction and extends it back to 5.3 Myr ago. We find that deep-sea temperature and sea level generally decreased through time, but distinctly out of synchrony, which is remarkable given the importance of ice-albedo feedbacks on the radiative forcing of climate. In particular, we observe a large temporal offset during the onset of Plio-Pleistocene ice ages, between a marked cooling step at 2.73 Myr ago and the first major glaciation at 2.15 Myr ago. Last, we tentatively infer that ice sheets may have grown largest during glacials with more modest reductions in deep-sea temperature.