What can we learn from the last million years of Earth history to better characterize important uncertainties in our understanding and predictions of anthropogenic climate change? To investigate this question, I compile a database of over 12,000 reconstructions of sea surface temperature, as well as reconstructions of polar temperatures, deep-sea temperatures, sea level, atmospheric greenhouse gases, and atmospheric dust. I create a probabilistic analysis framework to compare the reconstructions and to quantify numerous sources of uncertainty. Next, I use a Bayesian hierarchical model to assess patterns of sea surface temperature simultaneously over time and space, finding support for a "universal" curve of temperature response with latitude over the past million years. Third, I use the new database to create the first reconstruction of global average surface temperature over the past 800kyr. Previous reconstructions were limited to only a few isolated windows of time or specific locations. I find that climate models very likely (> 90% probability) underpredict global average cooling at the last glacial maximum (19-23kyr ago). I also find a remarkably stable relationship between global temperature and atmospheric carbon dioxide over the past 800kyr. Lastly, I estimate that the Earth's climate sensitivity (change in global temperature in response to a doubling of carbon dioxide concentrations) is 4.1K (2.1K-6.6K, 95% interval) and does not vary with time over the past 450kyr. These results significantly constrain the upper tail of climate sensitivity purely from the paleoclimate record and suggest that climate sensitivity values higher than 7K or less than 2K are not consistent with our current understanding of the Earth's past. Moreover, the median estimate of 4.1K is higher than 16 of the 19 IPCC global climate models. These results have important implications for assessing the risks of future climate change.