The greenhouse to icehouse climate transition from the Eocene into the Oligocene is well-documented by sea surface temperature records from the southwest Pacific and Antarctic margin that show evidence of pronounced long-term cooling. However, identification of a driving mechanism depends on a better understanding of whether this cooling was also present in terrestrial settings. Here, we present a semi-continuous terrestrial temperature record spanning from the middle Eocene to the early Oligocene (~41-33 Ma), using bacterial molecular fossils (biomarkers) preserved in a sequence of SE Australian lignites from two locations. We reconstruct terrestrial temperatures and compare them to existing sea-surface temperature records from the Southern Hemisphere from the middle Eocene to Early Oligocene.