Understanding the magnitude, timing and drivers of regional variations in paleotemperature is often challenging because of the lack of a similar proxy in every climate zone and differences in the temperature-proxy response relationship of the multiple proxies across large spatial scales. Borehole temperature data show promise for elucidating regional variation of paleotemperature because of their applicability in all climate zones. We reconstructed surface temperature histories for the past 2000 years, using borehole temperature data from four study regions within eastern Australia. Borehole temperatures across all four areas show warming since the 19th Century with most rapid warming occurring during the 20th Century. Reconstructions reveal significant spatial and temporal variation of paleotemperature between each region, with the south-east coast of the Australian mainland (Victoria) being the most different. Here, temperatures display a Little Ice Age (LIA) type response, decreasing during the 16th to 18th Century with a peak cold temperature of −0.6 °C during 1700 CE relative to the long term average spanning 0 to 1000 CE where temperature changes are negligible. Further, comparison with proxy data suggests temperature increases affected moisture balances in tropical and temperate regions differently. In the northern tropics, increased temperatures correlated with wetter conditions, while in the southern, more Mediterranean climate regions, warmer periods were generally drier.