Oxygen isotope measurements in Greenland ice demonstrate that a series of rapid warm-cold oscillations -called Dansgaard-Oeschger events- punctuated the last glaciation (Dansgard et al., 1993, doi:10.1038/364218a0). Here we present records of sea surface temperature from North Atlantic sediments spanning the past 90 kyr which contain a series of rapid temperature oscillations closely matching those in the ice-core record, confirming predictions that the ocean must bear the imprint of the Dansgaard-Oeschger events (Broecker et al., 1988, doi:10.1016/0033-5894(88)90082-8; 1990, doi:10.1029/PA005i004p00469). Moreover, we show that between 20 and 80 kyr ago, the shifts in ocean-atmosphere temperature are bundled into cooling cycles, lasting on average 10 to 15 kyr, with asymmetrical saw-tooth shapes. Each cycle culminated in an enormous discharge of icebergs into the North Atlantic (a 'Hein-rich event' (Bond et al., 1992, doi:10.1038/360245a0; Broecker et al., 1992, doi:10.1007/BF00193540), followed by an abrupt shift to a warmer climate. These cycles document a previously unrecognized link between ice sheet behaviour and ocean-atmosphere temperature changes. An important question that remains to be resolved is whether the cycles are driven by external factors, such as orbital forcing, or by inter-nal ice-sheet dynamics.