Climate of the last 11,000 years, the Holocene, is usually described as warm and stable. Benchmark temperature records from central Greenland ice cores show none of the large, abrupt variations that characterized the prior 100,000 years of glacial climate. Nor do they show any substantial trend, indicating at most 10--30C of cooling. Here we show that the slope waters east of the United States and Canada cooled 40--100C during the Holocene. Declining insolation, increasing convection in the Labrador Sea, and equatorward shifting of the Gulf Stream path may have caused the cooling.