Our understanding of past ocean-climate interactions has been hampered by a paucity of proxy reconstructions of physical ocean circulation parameters. Here we present the first detailed record of deepwater temperature variability that resolves Dansgaard-Oeschger climate fluctuations during the last glaciation. Results indicate a positive coupling between abrupt temperature changes over Greenland and in the deep North Atlantic that was mediated by perturbations to the Atlantic overturning circulation. The occurrence of sharp warming events at the center of the "Heinrich" stadials 4 and 5 further indicates that the response of the ocean interior was less static across these major climate events than has been previously apparent.