Recent extreme events such as the devastating 2003 European summer heat wave raise important questions about the possible causes of any underlying trends, or low-frequency variations, in regional climates. Here, we present new evidence that basin-scale changes in the Atlantic Ocean, probably related to the thermohaline circulation, have been an important driver of multidecadal variations in the summertime climate of both North America and western Europe. Our findings advance understanding of past climate changes and also have implications for decadal climate predictions.