Based on whole mtDNA sequencing of 14 samples from Northern Island Melanesia, we characterize three formerly unresolved branches of macrohaplogroup M that we call haplogroups M27, M28, and M29. Our 1,399 mtDNA control region sequences and a literature search indicate these haplogroups have extremely limited geographical distributions. Their coding region variation suggests diversification times older than the estimated date for the initial settlement of Northern Island Melanesia. This finding indicates that they were among the earliest mtDNA variants to appear in these islands or in the ancient continent of Sahul. These haplogroups from Northern Island Melanesia extend the existing schema for macrohaplogroup M, with many independent branches distributed across Asia, East Africa, Australia, and Near Oceania.