We sequenced the complete mitochondrial (mt) genomes of three insectivores: the long-eared hedgehog Hemiechinus auritus, the Japanese mole Mogera wogura, and the greater Japanese shrew-mole Urotrichus talpoides. These mtDNA data together with other previously sequenced mtDNAs were analyzed using a maximum likelihood method to infer their phylogenetic relationships among eutherians. Previous mitochondrial protein analyses used a simple model that did not consider site-heterogeneity, and Erinaceoidea (hedgehogs and moonrats) was placed at the basal eutherian position that is separated from Soricoidea (shrews) and Talpoidea (moles), suggesting the exclusion of the Erinaceoidea-Eulipotyphla tree. By including the new mtDNA sequences and introducing site-heterogeneity into the model, the Erinaceoidea-Eulipotyphla tree emerges as the best tree or as a tree with a log-likelihood score indistinguishable from that of the best tree. However, this conclusion depends on species sampling in Erinaceoidea, demonstrating the importance of both species sampling and use of an appropriate substitution model when inferring phylogenetic relationships.