The middle part of the Holocene epoch, between 6 and 4 thousand years ago, was characterized by crippling ‘megadroughts’ that led to the disruption of ancient civilizations across large parts of Africa and Asia. Indeed, collapse of the Akkadian Empire of Mesopotamia, the de-urbanization of the Indus Civilization, and the spread of pastoralism along the Nile, are all examples of societal shifts that have been linked with climate extremes (e.g., the ‘4.2 ka event’) during this period. Yet, the extent of these climate extremes in mainland Southeast Asia (MSEA) has never been defined. This is despite archeological evidence showing a shift in human settlement patterns across the region during this period. We report evidence from cave stalagmite climate records indicating a major decrease of monsoon rainfall in MSEA during the mid- to late Holocene, coincident with African monsoon failure during the end of the ‘Green Sahara’. Through a set of climate modeling experiments, we show that reduced vegetation and increased dust emissions during the Green Sahara termination shifted the Walker circulation eastward and cooled the Indian Ocean, causing a reduction in monsoon rainfall in MSEA. Our results indicate that vegetation-dust climate feedbacks from Sahara drying may have been the catalyst for societal shifts in MSEA via ocean atmospheric teleconnections.