Island Southeast Asia (ISEA) was first colonized by modern humans at least 45,000 years ago, but the extent to which the modern inhabitants trace their ancestry to the first settlers is a matter of debate. It is widely held, in both archaeology and linguistics, that they are largely descended from a second wave of dispersal, proto-Austronesian-speaking agriculturalists who originated in China and spread to Taiwan approximately 5,500 years ago. From there, they are thought to have dispersed into ISEA approximately 4,000 years ago, assimilating the indigenous populations. Here, we demonstrate that mitochondrial DNA diversity in the region is extremely high and includes a large number of indigenous clades. Only a fraction of these date back to the time of first settlement, and the majority appear to mark dispersals in the late-Pleistocene or early-Holocene epoch most likely triggered by postglacial flooding. There are much closer genetic links to Taiwan than to the mainland, but most of these probably predated the mid-Holocene "Out of Taiwan" event as traditionally envisioned. Only approximately 20% at most of modern mitochondrial DNAs in ISEA could be linked to such an event, suggesting that, if an agriculturalist migration did take place, it was demographically minor, at least with regard to the involvement of women.