The tropical archipelago of Wallacea contains thousands of individual islands interspersed between mainland Asia and Near Oceania, and marks the location of a series of ancient oceanic voyages leading to the peopling of Sahul—i.e., the former continent that joined Australia and New Guinea at a time of lowered sea level—by 50,000 years ago. Despite the apparent deep antiquity of human presence in Wallacea, prior population history research in this region has been hampered by patchy archaeological and genetic records and is largely concentrated upon more recent history that follows the arrival of Austronesian seafarers ~3000–4000 years ago (3–4 ka). To shed light on the deeper history of Wallacea and its connections with New Guinea and Australia, we performed phylogeographic analyses on 656 whole mitogenomes from these three regions, including 186 new samples from eight Wallacean islands and three West Papuan populations. Our results point to a surprisingly dynamic population history in Wallacea, marked by two periods of extensive demographic change concentrated around the Last Glacial Maximum ~15 ka and post-Austronesian contact ~3 ka. These changes appear to have greatly diminished genetic signals informative about the original peopling of Sahul, and have important implications for our current understanding of the population history of the region.