Magnesium/calcium ratios in benthic foraminifera (Cibicidoides pachyderma) from a sediment core on the Laurentian Slope (1854 m) exhibit strong millennial-scale fluctuations during the past 4000 years. We convert these data to seawater paleotemperatures using a new monospecific linear equation. Results suggest that the temperature of upper North Atlantic Deep Water (dominated by Labrador Seawater today) has varied by at least 2¿C during the late Holocene. Millennial scale coolings coincide with previously identified periods of increased drift ice and regional glacier advances, including the Little Ice Age. Paired oxygen isotope measurements indicate that salinity and perhaps density were reduced during the cold periods. We discuss possible mechanisms for transmitting this cold, fresh signal from surface waters to intermediate depths. Our reconstructed late Holocene ranges in upper North Atlantic Deep Water properties greatly exceed those of the instrumental record and imply that large changes may be yet to come.