Fungi which produce their spores on the dung of large herbivores show promise as indicators of the distribution and relative abundance of large herbivores in past environments. Recently, several studies have used counts of spores of such fungi, Sporormiella in particular, to resolve the timing and reveal the ecological consequences of extinction of Pleistocene megafauna. However, there are several problems in the interpretation of the dung-fungus proxy, relating mostly to taphonomic effects on spore accumulation. Here, we describe these problems and show how they can be solved, using new data from the Lynch's Crater site in northeastern Australia. Effects of variation in spore accumulation in relation to position in the sedimentary basin can be controlled by comparing cores from different locations; temporal variation in spore accumulation rates can be attributed to changes in herbivore populations, as distinct from time-varying taphonomic effects, by comparing trends in fungi exclusively associated with herbivore dung to trends for fungi that also sporulate on other substrates; effects of changing vegetation composition can be removed by measuring spore influx rates rather than expressing counts relative to the pollen sum. At Lynch's Crater, these approaches increase our confidence that a decline in dung fungi at ~40. ka indicates an unprecedented drop in biomass of large herbivores. We also show that before this decline, the biomass of large herbivores at this site was evidently similar to that in North America and western Europe.