In order to adapt to the changing climate, not only changes in the mean state but also the magnitude and change of climate variability have to be known.Whereas synoptic to interannual variations in the climate system are well documented and current climate models are generally able to simulate them realistically, much less is known about the amplitude and the mechanisms of climate variability on longer time-scales. Estimating that variability is the basis for the detection and attribution of the anthropogenic component, determines the range of plausible future climate changes and also provides information about the time-scales of the earth system components. Paleoclimate archives such as ice-core and marine sediment records can provide the needed information about climate variability but are sparse, inherently noisy and and at times provide contradictory evidence. This hampered quantitative reconstructions of climate variability and systematic testing of the variability simulated from climate models. In the last years, several advances have been made to better extract climate variability estimates from climate archives. These include a better characterisation of the non-climate effects and the proxy response based on replicate, multi-proxy and core-top compilations, proxy system models bridging the gap between climate and proxy variations as well as novel statistical techniques tailored to separate climate from noise components. Based on these advances we were able to considerably improve our understanding of the present climate variability as well as to estimate how climate variability responds to a changing climate. I will discuss recent advances in the toolbox of teasing out climate variability from marine and ice-core based proxy records and also point out future directions how to enhance the use of the paleoclimate record for quantitatively constraining present and future climate variability.