Between 5 and 4 thousand years ago, crippling megadroughts led to the disruption of ancient civilizations across parts of Africa and Asia, 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 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 modeling experiments, we show that reduced vegetation and increased dust loads 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.