Variations in regional temperature have widespread implications for society, but our understanding of the amplitude and origin of long-term natural variability is insufficient for accurate regional projections. This is especially the case for terrestrial temperature variability, which is currently thought to be weak over long timescales. By performing spectral analysis on climate reconstructions, produced using sedimentary pollen records from the Northern Hemisphere over the last 8,000 years, coupled with instrumental data, we provide a comprehensive estimate of regional temperature variability from annual to millennial timescales. We show that short-term random variations are overprinted by strong ocean-driven climate variability on multi-decadal and longer timescales. This may cause substantial and potentially unpredictable regional climatic shifts in the coming century, in contrast to the relatively muted and homogeneous warming projected by climate models. Due to the marine influence, regions characterized by stable oceanic climate at sub-decadal timescales experience stronger long-term variability, and continental regions with higher sub-decadal variability show weaker long-term variability. This fundamental relationship between the timescales provides a unique insight into the emergence of a marine-driven low-frequency regime governing terrestrial climate variability and sets the basis to project the amplitude of temperature fluctuations on multi-decadal timescales and longer.