Understanding the extent to which Atlantic sea surface temperatures (SSTs) are predictable is important due to the strong climate impacts of Atlantic SST on Atlantic hurricanes and temperature and precipitation over adjacent landmasses. However, models differ substantially on the degree of predictability of Atlantic SST and upper-ocean heat content (UOHC). In this work, a lower bound on predictability time scales for SST and UOHC in the North Atlantic is estimated purely from gridded ocean observations using a measure of the decorrelation time scale based on the local autocorrelation. Decorrelation time scales for both wintertime SST and UOHC are longest in the subpolar gyre, with maximum time scales of about 4-6 years. Wintertime SST and UOHC generally have similar decorrelation time scales, except in regions with very deep mixed layers, such as the Labrador Sea, where time scales for UOHC are much larger. Spatial variations in the wintertime climatological mixed layer depth explain 51%-73% (range for three datasets analyzed) of the regional variations in decorrelation time scales for UOHC and 26%-40% (range for three datasets analyzed) of the regional variations in decorrelation time scales for wintertime SST in the extratropical North Atlantic. These results suggest that to leading order decorrelation time scales for UOHC are determined by the thermal memory of the ocean.