Speleothems represent important archives of terrestrial climate variation that host a variety of proxy signals and are also highly amenable to radiometric age determination. Although speleothems have been forming on Earth for at least 400 million years, most studies rely upon the U-Th chronometer which extends only to the mid Pleistocene, leaving important questions over their longer-term preservation potential. To date, older records, exploiting the advantages of the U-Pb chronometer, remain fragmentary 'snapshots in time'. Here we demonstrate the viability of speleothems as deep time climate archives by showing that a vast system of shallow caves beneath the arid Nullarbor plain of southern Australia, the world's largest exposed karst terrain, formed largely within the Pliocene epoch, with a median age of 4.2 Ma, and that, in these caves, even the most delicate formations date from this time. The long-term preservation of regional-scale cave networks such as this demonstrates that abundant speleothem archives do survive to permit the reconstruction of climates and environments for much older parts of Earth history than the ~600 ka period to which most previous studies have been limited.