We reconstructed three time series of last glacial-to-present deep-sea temperature from deep and intermediate water sediment cores from the western North Atlantic using Mg/Ca ratios of benthic ostracode shells. Although the Mg/Ca data show considerable variability (“scatter”) that is common to single-shell chemical analyses, comparisons between cores, between core top shells and modern bottom water temperatures (BWT), and comparison to other paleo-BWT proxies, among other factors, suggest that multiple-shell average Mg/Ca ratios provide reliable estimates of BWT history at these sites. The BWT records show not only glacial-to-interglacial variations but also indicate BWT changes during the deglacial and within the Holocene interglacial stage. At the deeper sites (4500- and 3400-m water depth), BWT decreased during the last glacial maximum (LGM), the late Holocene, and possibly during the Younger Dryas. Maximum deep-sea warming occurred during the latest deglacial and early Holocene, when BWT exceeded modern values by as much as 2.5°C. This warming was apparently most intense around 3000 m, the depth of the modern-day core of North Atlantic deep water (NADW). The BWT variations at the deeper water sites are consistent with changes in thermohaline circulation: warmer BWT signifies enhanced NADW influence relative to Antarctic bottom water (AABW). Thus maximum NADW production and associated heat flux likely occurred during the early Holocene and decreased abruptly around 6500 years B.P., a finding that is largely consistent with paleonutrient studies in the deep North Atlantic. BWT changes in intermediate waters (1000-m water depth) of the subtropical gyre roughly parallel the deep BWT variations including dramatic mid-Holocene cooling of around 4°C. Joint consideration of the Mg/Ca-based BWT estimates and benthic oxygen isotopes suggests that the cooling was accompanied by a decrease in salinity at this site. Subsequently, intermediate waters warmed to modern values that match those of the early Holocene maximum of ∼7°C. Intermediate water BWT changes must also be driven by changes in ocean circulation. These results thus provide independent evidence that supports the hypothesis that deep-ocean circulation is closely linked to climate change over a range of timescales regardless of the mean climate state. More generally, the results further demonstrate the potential of benthic Mg/Ca ratios as a tool for reconstructing past ocean and climate conditions.