The moisture balance across northern and central Australia is dominated by changes in the strength of the Australian Summer Monsoon. Lake-level records that record changes in monsoon strength on orbital timescales are most consistent with a Northern Hemisphere insolation control on monsoon strength, a result consistent with recent modeling studies. A weak Holocene monsoon relative to monsoon strength 65-60 ka, despite stronger forcing, suggests a changed monsoon regime after 60 ka. Shortly after 60 ka humans colonized Australia and all of Australia's largest mammals became extinct. Between 60 and 40 ka Australian climate was similar to present and not changing rapidly. Consequently, attention has turned toward plausible human mechanisms for the extinction, with proponents for over-hunting, ecosystem change, and introduced disease. To differentiate between these options we utilize isotopic tracers of diet preserved in eggshells of two large, flightless birds to track the status of ecosystems before and after human colonization. More than 800 dated eggshells of the Australian emu (Dromaius novaehollandiae), an opportunistic, dominantly herbivorous feeder, provide a 140-kyr dietary reconstruction that reveals unprecedented reduction in the bird's food resources about 50 ka, coeval in three distant regions. These data suggest a tree/shrub savannah with occasionally rich grasslands was converted abruptly to the modern desert scrub. The diet of the heavier, extinct Genyornis newtoni, derived from >550 dated eggshells, was more restricted than in co-existing Dromaius, implying a more specialized feeding strategy. We suggest that generalist feeders, such as Dromaius, were able to adapt to a changed vegetation regime, whereas more specialized feeders, such as Genyornis, became extinct. We speculate that ecosystem collapse across arid and semi-arid zones was a consequence of systematic burning by early humans. We also suggest that altered climate feedbacks linked to changes in vegetation may have weakened the penetration of monsoon moisture into the continental interior, explaining the failure of the Holocene monsoon. Climate modeling suggests a vegetation shift may reduce monsoon rain in the interior by as much as 50%.