- 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 400,000 years) tem- perature (assumed to represent the annual mean) changes reflected by data obtained from four ice-cores (two from Antarctic and two from Greenland). We perform cor- relation analysis using the detrended fluctuation analysis which can eliminate higher order trends from the data. We show that changes in the delta-18O and delta-D (tem- perature proxies) are strongly long-range correlated over tens of thousands of years up to 100,000 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. We relate these volatility correlations to a wide multifractal spectrum for climate change.