A fundamental statistic of climate variability is its spatiotemporal correlation function. Its complex structure can be concisely summarized by a frequency-dependent measure of the effective spatial degrees of freedom (ESDOF). Here we present, for the first time, frequency-dependent ESDOF estimates of global natural surface temperature variability from purely instrumental measurements, using the HadCRUT4 dataset (1850-2014). The approach is based on a newly developed method for estimating the frequency-dependent spatial correlation function from gappy data fields. Results reveal a multicomponent structure of the spatial correlation function, including a large-amplitude short-distance component (with weak time scale dependence) and a small-amplitude long-distance component (with increasing relative amplitude toward the longer time scales). Two frequency-dependent ESDOF measures are applied, each responding mainly to either of the two components. Both measures exhibit a significant ESDOF reduction from monthly to multidecadal time scales, implying an increase of the effective spatial scale of natural surface temperature fluctuations. Moreover, it is found that a good approximation to the global number of equally spaced samples needed to estimate the variance of global mean temperature is given, at any frequency, by the greater one of the two ESDOF measures, decreasing from ;130 at monthly to ;30 at multidecadal time scales. Finally, the multicomponent structure of the correlation function together with the detected ESDOF scaling properties indicate that the ESDOF reduction toward the longer time scales cannot be explained simply by diffusion acting on stochastically driven anomalies, as it might be suggested f rom simple stochastic-diffusive energy balance models.