Using multi-scale ideas from wavelet analysis, we extend singular-spectrum analysis (SSA) to the study of nonstationary time series of length $N$ whose intermittency can give rise to the divergence of their variance. SSA relies on the construction of the lag-covariance matrix C on M lagged copies of the time series over a fixed window width W to detect the regular part of the variability in that window in terms of the minimal number of oscillatory components; here W = M Dt, with Dt the time step. The proposed multi-scale SSA is a local SSA analysis within a moving window of width M <= W <= N. Multi-scale SSA varies W, while keeping a fixed W/M ratio, and uses the eigenvectors of the corresponding lag-covariance matrix C_M as a data-adaptive wavelets; successive eigenvectors of C_M correspond approximately to successive derivatives of the first mother wavelet in standard wavelet analysis. Multi-scale SSA thus solves objectively the delicate problem of optimizing the analyzing wavelet in the time-frequency domain, by a suitable localization of the signal's covariance matrix. We present several examples of application to synthetic signals with fractal or power-law behavior which mimic selected features of certain climatic and geophysical time series. A real application is to the Southern Oscillation index (SOI) monthly values for 1933-1996. Our methodology highlights an abrupt periodicity shift in the SOI near 1960. This abrupt shift between 4 and 3 years supports the Devil's staircase scenario for the El Nino/Southern Oscillation phenomenon.