Melanesian populations are known for their diversity, but it has been hard to grasp the pattern of the variation or its underlying dynamic. Using 1,223 mitochondrial DNA (mtDNA) sequences from hypervariable regions 1 and 2 (HVR1 and HVR2) from 32 populations, we found the among-group variation is structured by island, island size, and also by language affiliation. The more isolated inland Papuan-speaking groups on the largest islands have the greatest distinctions, while shore dwelling populations are considerably less diverse (at the same time, within-group haplotype diversity is less in the most isolated groups). Persistent differences between shore and inland groups in effective population sizes and marital migration rates probably cause these differences. We also add 16 whole sequences to the Melanesian mtDNA phylogenies. We identify the likely origins of a number of the haplogroups and ancient branches in specific islands, point to some ancient mtDNA connections between Near Oceania and Australia, and show additional Holocene connections between Island Southeast Asia/Taiwan and Island Melanesia with branches of haplogroup E. Coalescence estimates based on synonymous transitions in the coding region suggest an initial settlement and expansion in the region at approximately 30-50,000 years before present (YBP), and a second important expansion from Island Southeast Asia/Taiwan during the interval approximately 3,500-8,000 YBP. However, there are some important variance components in molecular dating that have been overlooked, and the specific nature of ancestral (maternal) Austronesian influence in this region remains unresolved.