The nature of the Australian climate at about the time of rapid megafaunal extinctions and humans arriving in Australia is poorly understood and is an important element in the contentious debate as to whether humans or climate caused the extinctions. Here we present a new paleoshoreline chronology that extends over the past 100 k.y. for Lake Mega-Frome, the coalescence of Lakes Frome, Blanche, Callabonna and Gregory, in the southern latitudes of central Australia. We show that Lake Mega-Frome was connected for the last time to adjacent Lake Eyre at 50-47 ka, forming the largest remaining interconnected system of paleolakes on the Australian continent. The final disconnection and a progressive drop in the level of Lake Mega-Frome represents a major climate shift to aridification that coincided with the arrival of humans and the demise of the megafauna. The supply of moisture to the Australian continent at various times in the Quaternary has commonly been ascribed to an enhanced monsoon. This study, in combination with other paleoclimate data, provides reliable evidence for periods of enhanced tropical and enhanced Southern Ocean sources of water filling these lakes at different times during the last full glacial cycle.