Archaeology, linguistics, and existing genetic studies indicate that Oceania was settled by two major waves of migration. The first migration took place approximately 40 thousand years ago and these migrants, Papuans, colonized much of Near Oceania. Approximately 3.5 thousand years ago, a second expansion of Austronesian-speakers arrived in Near Oceania and the descendants of these people spread to the far corners of the Pacific, colonizing Remote Oceania. To assess the female contribution of these two human expansions to modern populations and to investigate the potential impact of other migrations, we obtained 1,331 whole mitochondrial genome sequences from 34 populations spanning both Near and Remote Oceania. Our results quantify the magnitude of the Austronesian expansion and demonstrate the homogenizing effect of this expansion on almost all studied populations. With regards to Papuan influence, autochthonous haplogroups support the hypothesis of a long history in Near Oceania, with some lineages suggesting a time depth of 60 thousand years, and offer insight into historical interpopulation dynamics. Santa Cruz, a population located in Remote Oceania, is an anomaly with extreme frequencies of autochthonous haplogroups of Near Oceanian origin; simulations to investigate whether this might reflect a pre-Austronesian versus Austronesian settlement of the island failed to provide unequivocal support for either scenario.