The "Polynesian motif" defines a lineage of human mtDNA that is restricted to Austronesian-speaking populations and is almost fixed in Polynesians. It is widely thought to support a rapid dispersal of maternal lineages from Taiwan ~4000 years ago (4 ka), but the chronological resolution of existing control-region data is poor, and an East Indonesian origin has also been proposed. By analyzing 157 complete mtDNA genomes, we show that the motif itself most likely originated >6 ka in the vicinity of the Bismarck Archipelago, and its immediate ancestor is >8 ka old and virtually restricted to Near Oceania. This indicates that Polynesian maternal lineages from Island Southeast Asia gained a foothold in Near Oceania much earlier than dispersal from either Taiwan or Indonesia 3-4 ka would predict. However, we find evidence in minor lineages for more recent two-way maternal gene flow between Island Southeast Asia and Near Oceania, likely reflecting movements along a "voyaging corridor" between them, as previously proposed on archaeological grounds. Small-scale mid-Holocene movements from Island Southeast Asia likely transmitted Austronesian languages to the long-established Southeast Asian colonies in the Bismarcks carrying the Polynesian motif, perhaps also providing the impetus for the expansion into Polynesia.