Aiming to describe spatio-temporal climate variability on decadal-to-centennial time scales and longer, we analyzed a data set of 26 proxy records extending back 1,000–5,000 years; all records chosen were calibrated to yield temperatures. The seven irregularly sampled series in the data set were interpolated to a regular grid by optimized methods and then two advanced spectral methods—namely singular-spectrum analysis (SSA) and the continuous wavelet transform—were applied to individual series to separate significant oscillations from the high noise background. This univariate analysis identified several common periods across many of the 26 proxy records: a millennial trend, as well as oscillations of about 100 and 200 years, and a broad peak in the 40–70-year band. To study common NH oscillations, we then applied Multichannel SSA. Temperature variations on time scales longer than 600 years appear in our analysis as a dominant trend component, which shows climate features consistent with the Medieval Warm Period and the Little Ice Age. Statistically significant NH-wide peaks appear at 330, 250 and 110 years, as well as in a broad 50–80-year band. Strong variability centers in several bands are located around the North Atlantic basin and are in phase opposition between Greenland and Western Europe.