Modern humans have been living in Island Southeast Asia (ISEA) for at least 50,000 years. Largely because of the influence of linguistic studies, however, which have a shallow time depth, the attention of archaeologists and geneticists has usually been focused on the last 6,000 years--in particular, on a proposed Neolithic dispersal from China and Taiwan. Here we use complete mitochondrial DNA (mtDNA) genome sequencing to spotlight some earlier processes that clearly had a major role in the demographic history of the region but have hitherto been unrecognized. We show that haplogroup E, an important component of mtDNA diversity in the region, evolved in situ over the last 35,000 years and expanded dramatically throughout ISEA around the beginning of the Holocene, at the time when the ancient continent of Sundaland was being broken up into the present-day archipelago by rising sea levels. It reached Taiwan and Near Oceania more recently, within the last approximately 8,000 years. This suggests that global warming and sea-level rises at the end of the Ice Age, 15,000-7,000 years ago, were the main forces shaping modern human diversity in the region.