The variability of sea surface temperatures (SSTs) at multidecadal and longer timescales is poorly constrained, primarily because instrumental records are short and proxy records are noisy. Through applying a new noise filtering technique to a global network of late Holocene SST proxies, we estimate SST variability between annual and millennial timescales. Filtered estimates of SST variability obtained from coral, foraminifer, and alkenone records are shown to be consistent with one another and with instrumental records in the frequency bands at which they overlap. General circulation models, however, simulate SST variability that is systematically smaller than instrumental and proxy-based estimates. Discrepancies in variability are largest at low latitudes and increase with timescale, reaching two orders of magnitude for tropical variability at millennial timescales. This result implies major deficiencies in observational estimates or model simulations, or both, and has implications for the attribution of past variations and prediction of future change.