Modern humans have occupied New Guinea and the nearby Bismarck and Solomon archipelagos of Island Melanesia for at least 40,000 years. Previous mitochondrial DNA (mtDNA) studies indicated that two common lineages in this region, haplogroups P and Q, were particularly diverse, with the coalescence for P considered significantly older than that for Q. In this study, we expand the definition of haplogroup Q so that it includes three major branches, each separated by multiple mutational distinctions (Q1, equivalent to the earlier definition of Q, plus Q2 and Q3). We report three whole-mtDNA genomes that establish Q2 as a major Q branch. In addition, we describe 314 control region sequences that belong to the expanded haplogroups P and Q from our Southwest Pacific collection. The coalescence dates for the largest P and Q branches (P1 and Q1) are similar to each other (approximately 50,000 years old) and considerably older than prior estimates. Newly identified Q2, which was found in Island Melanesian samples just to the east, is somewhat younger by more than 10,000 years. Our coalescence estimates should be more reliable than prior ones because they were based on significantly larger samples as well as complete mtDNA-coding region sequencing. Our estimates are roughly in accord with the current suggested dates for the first settlement of New Guinea-Sahul. The phylogeography of P and Q indicates almost total (female) isolation of ancient New Guinea-Island Melanesia from Australia that may have existed from the time of the first settlement. While Q subsequently diversified extensively in New Guinea-Island Melanesia, it has not been found in Australia. The only shared mtDNA haplogroup between Australia and New Guinea identified to date remains one minor branch of P.