Using multi-scale ideas from wavelet analysis, we extend singular-spectrum analysis (SSA) to the study of nonstationary time series, including the case where intermittency gives rise to the divergence of their variance. The wavelet transform resembles a local Fourier transform within a finite moving window whose width W, proportional to the major period of interest, is varied to explore a broad range of such periods. SSA, on the other hand, relies on the construction of the lag-correlation 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[Delta]t with [Delta]t as the time step. The proposed multi-scale SSA is a local SSA analysis within a moving window of width M<=W<=N, where N is the length of the time series. Multi-scale SSA varies W, while keeping a fixed W/M ratio, and uses the eigenvectors of the corresponding lag-correlation matrix C(M) as 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 correlation matrix. We present several examples of application to synthetic signals with fractal or power-law behavior which mimic selected features of certain climatic or geophysical time series. The method is applied next to the monthly values of the Southern Oscillation Index (SOI) for 1933-1996; the SOI time series is widely believed to capture major features of the El Niño/Southern Oscillation (ENSO) in the Tropical Pacific. Our methodology highlights an abrupt periodicity shift in the SOI near 1960. This abrupt shift between 5 and 3 years supports the Devil's staircase scenario for the ENSO phenomenon (preliminary results of this study were presented at the XXII General Assembly of the European Geophysical Society, Vienna, May 1997, and at the Fall Meeting of the American Geophysical Union, San Francisco, December 1997).