We present a long-term record of terrestrial climate change for the early Paleogene of the Southern Hemisphere that complements previously reported marine temperature records. Using the MBT'-CBT proxy, based on the distribution of soil bacterial glycerol dialkyl glycerol tetraether lipids, we reconstructed mean annual air temperature (MAT) from the Middle Paleocene to Middle Eocene (62 to 42 Ma) for southern New Zealand. This record is consistent with temperature estimates derived from leaf fossils and palynology, as well as previously published MBT'-CBT records, which provides confidence in absolute temperature estimates. Our record indicates that through this interval, temperatures were typically 5ºC warmer than those of today at such latitudes, with more pronounced warming during the Early Eocene Climate Optimum (EECO; ~50 Ma) when MAT was ~20ºC. Moreover, the EECO MATs are similar to those determined for Antarctica, with a weak high latitude terrestrial temperature gradient (~5ºC) developing by the middle Eocene. We also document a short-lived cooling episode in the early Late Paleocene when MAT was comparable to present. This record corroborates the trends documented by sea surface temperature (SST) proxies, although absolute SSTs are up to 6°C warmer than MATs. Although the high calibration error of the MBT'-CBT proxy dictates caution, the good match between our MAT results and modelled temperatures supports the suggestion that SST records suffer from a warm (summer?) bias, particularly during times of peak warming.