Previous studies indicated weak long-range correlated behavior in daily temperature variations from their annual average. These temperature variations are found to be correlated over a decade. Here we study long-term (more than 100000 years) annual temperature changes reflected by data obtained from four ice-cores (two from the south-pole and two from the north-pole). We perform correlation analysis using the following techniques: (i) uneven sampled Fourier transform technique and (ii) the detrended fluctuation analysis which can eliminate higher order trends from the data. We show that changes in the delta-18O and delta-D (temperature proxies) are strongly long-range correlated over tens of thousands of years. Moreover, we also study the correlation properties of the magnitudes of the increments of climate changes (volatility) and find highly correlated behavior; these volatility correlations indicate strong nonlinearity of the underlying processes of climate changes. Our results suggest a wide multifractal spectrum for climate change.