We review the statistical methods currently in use to estimate past changes in climate. These methods encompass the full gamut of statistical modeling approaches, ranging from simple regression up to nonparametric spatiotemporal Bayesian models. Often the full inferential challenge is broken down into many submodels each of which may involve multiple stochastic components, and occasionally mechanistic or process-based models too. We argue that many of the traditional approaches are simplistic in their structure, handling, and presentation of uncertainty, and that newer models (which incorporate mechanistic aspects alongside statistical models) provide an exciting research agenda for the next decade. We hope that policy-makers and those charged with predicting future climate change will increasingly use probabilistic paleoclimate reconstructions to calibrate their forecasts, learn about key natural climatological parameters, and make appropriate decisions concerning future climate change. Remarkably few statisticians have involved themselves with paleoclimate reconstruction, and we hope that this article inspires more to take up the challenge.