Evidence of past climate variations are stored in polar ice caps and indicate glacial-interglacial cycles of ~100 kyr. Using advanced scaling techniques we study the long-range correlation properties of temperature proxy records of four ice cores from Antarctica and Greenland. These series are long-range correlated in the time scales of 1--100 kyr. We show that these time series are nonlinear for time scales of 1--100 kyr as expressed by temporal long-range correlations of magnitudes of temperature increments and by a broad multifractal spectrum. Our results suggest that temperature increments appear in clusters of big and small increments-a big (positive or negative) climate change is most likely followed by a big (positive or negative) climate change and a small climate change is most likely followed by a small climate change.