The study of arid palaeoenvironments is often frustrated by the poor or non-existent preservation of plant and animal material, yet these environments are of considerable environmental importance. The analysis of pollen and macrofossils isolated from herbivore middens has been an invaluable source of information regarding past environments and the nature of ecological fluctuations within arid zones. The application of ancient DNA (aDNA) techniques to hot, arid zone middens remains unexplored. This paper attempts to retrieve and characterise aDNA from four Southern Hemisphere fossil middens; three located in hot, arid regions of Australia and one sample from South Africa's Western Cape province. The middens are dated to between 30,490 (±380) and 710 (±70) cal yr BP. The Brockman Ridge midden in this study is potentially the oldest sample from which aDNA has been successfully extracted in Australia. The application of high-throughput sequencing approaches to profile the biotic remains preserved in midden material has not been attempted to date and this study clearly demonstrates the potential of such a methodology. In addition to the taxa previously detected via macrofossil and palynological analyses, aDNA analysis identified unreported plant and animal taxa, some of which are locally extinct or endemic. The survival and preservation of DNA in hot, arid environments is a complex and poorly understood process that is both sporadic and rare, but the survival of DNA through desiccation may be important. Herbivore middens now present an important source of material for DNA metabarcoding studies of hot, arid palaeoenvironments and can potentially be used to analyse middens in these environments throughout Australia, Africa, the Americas and the Middle East.