In recent decades the surface water temperature and salinity in the Labrador Sea have been influenced by atmospheric circulation patterns, such as the North Atlantic Oscillation (NAO), as well as a trend to increasingly warm atmospheric temperatures in recent years. These changes are concerning, given the important role that temperature and salinity have on deep convection in the Labrador Sea. Yet, due to the shortness of available records, the long-term patterns of climate variability in the region are not clear. Here, a diatom-based reconstruction of summer sea-surface temperature (SST) developed from Trinity Bay, Newfoundland, provides insight into variations of SST since 7.2 cal ka BP in the southwestern Labrador Sea. The results show that the Holocene Thermal Maximum (HTM) lasted until c. 5.2 cal ka BP, which was followed by a gradual cooling trend overprinted by centennial temperature fluctuations of 1-2 degrees C. Long-term cooling was likely the result of declining Northern Hemisphere orbital summer insolation, potentially amplified by long-term changes in surface and bottom water salinity, which led to a gradual reduction in the stratification of the water column. Centennial fluctuations in temperature vary in-phase with reconstructed variations in the NAO, supporting a consistent relationship between atmospheric circulation and SST over centennial-millennial timescales. Other factors influencing the SST variability may have been solar forcing during the mid-Holocene and variations in the strength of the subpolar gyre during the late-Holocene. The most prolonged cool period at 5.2-4.1 cal ka BP coincides with sharply reduced salinity in the Labrador Sea and a weakening of deep ventilation in the northeast Atlantic, highlighting a period with altered ocean surface conditions and circulation across the northern North Atlantic.