Resolving faunal responses to Pleistocene climate change is vital for differentiating human impacts from other drivers of ecological change. While 90% of Australia's large mammals were extinct by ca. 45 ka, their responses to glacial-interglacial cycling have remained unknown, due to a lack of rigorous biostratigraphic studies and the rarity of terrestrial climatic records that can be related directly to faunal records. We present an analysis of faunal data from the Naracoorte Caves in southeastern Australia, which are unique not only because of the species richness and time-depth of the assemblages that they contain, but also because this faunal record is directly comparable with a 500 k.y. speleothem-based record of local effective moisture. Our data reveal that, despite significant population fluctuations driven by glacial-interglacial cycling, the species composition of the mammal fauna was essentially stable for 500 k.y. before the late Pleistocene extinctions. Larger species declined during a drier interval between 270 and 220 ka, likely reflecting range contractions away from Naracoorte, but they then recovered locally, persisting well into the late Pleistocene. Because the speleothem record and prior faunal response imply that local conditions should have been favorable for megafauna until at least 30 ka, climate change is unlikely to have been the principal cause of the extinctions.