Recent studies suggest that extinction of Pleistocene megafauna had large impacts on the structure and functioning of ecosystems, including increased fire and shifts in vegetation state. We argue that the ecological effects of mega-herbivore extinction are likely to have varied geographically, and might have been reduced in environments of low productivity. We tested this at Caledonia Fen, a cool, high-elevation site in southeast Australia with a palynological record reaching back approximately 140 ka. The dung fungus Sporormiella indicated that large herbivores were present through most of the early part of the last glacial cycle, but declined abruptly between 50-40 ka and did not recover. This event corresponds with evidence for continent-wide extinction of Australia's Pleistocene megafauna at that time. An earlier episode of low Sporormiella occurrence coincided with evidence of raised water levels in the fen. Changes in wetland conditions can alter the accumulation of Sporormiella, but there was no such change when Sporormiella counts fell in the period 50-40 ka. We found no evidence that the decline in Sporormiella triggered increased fire or a change in vegetation, which remained a low grass/shrub steppe. This contrasts with a warmer and more humid site, Lynch's Crater in northeast Australia, where decline of dung fungi was followed by increased fire and transition from mixed sclerophyll forest and rainforest to uniform sclerophyll forest. Our results suggest that the magnitude of ecological responses to Pleistocene megafaunal extinction varied geographically, under the control of regional climates.