Estimates of past climate derived from borehole temperatures are assuming a greater importance in context of the millennial temperature variation debate. However, recovery of these signals is usually performed with regularization which can potentially lead to underestimation of past variation when noise is present. In this work Bayesian inference is applied to this problem with no explicit regularization. To achieve this Reversible Jump Markov chain Monte Carlo is employed, and this allows models of varying complexity (i.e. variable dimensions) to be sampled so that it is possible to infer the level of ground surface temperature (GST) history resolution appropriate to the data. Using synthetic examples, we show that the inference of the GST signal back to more than 500 yr is robust given boreholes of 500 m depth and moderate noise levels and discuss the associated uncertainties. We compare the prior information we have used with the inferred posterior distribution to show which parts of the GST reconstructions are independent of this prior information. We demonstrate the application of the method to real data using five boreholes from southern England. These are modelled both individually and jointly, and appear to indicate a spatial trend of warming over 500 yr across the south of the country.