We look at the higher-order phylogeny of mammals, analyzing in detail the complete mtDNA sequences of more than 40 species. We test the support for several proposed superordinal relationships. To this end, we apply a number of recently programmed methods and approaches, plus better-established methods. New pairwise tests show highly significant evidence that amino acid frequencies are changing among nearly all the genomes studied when unvaried sites are ignored. LogDet amino acid distances, with modifications to take into account invariant sites, are combined with bootstrapping and the Neighbor Joining algorithm to account for these violations of standard models. To weight the more slowly evolving sites, we exclude the more rapidly evolving sites from the data by using “site stripping”. This leads to changing optimal trees with nearly all methods. The bootstrap support for many hypotheses varies widely between methods, and few hypotheses can claim unanimous support from these data. Rather, we uncover good evidence that many of the earlier branching patterns in the placental subtree could be incorrect, including the placement of the root. The tRNA genes, for example, favor a split between the group hedgehog, rodents, and primates versus all other sequenced placentals. Such a grouping is not ruled out by the amino acid sequence data. A grouping of all rodents plus rabbit, the old Glires hypothesis, is also feasible with stripped amino acid data, and rodent monophyly is also common. The elephant sequence allows confident rejection of the older taxon Ferungulata (Simpson, 1945). In its place, the new taxa Scrotifera and Fereuungulata are defined. A new likelihood ratio test is used to detect differences between the optimal tree for tRNA versus that for amino acids. While not clearly significant as made, some results indicate the test is tending towards significance with more general models of evolution. Individual placement tests suggest alternative positions for hedgehog and elephant. Congruence arguments to support elephant and armadillo together are striking, suggesting a superordinal group composed of Xenarthra and African endemic mammals, which in turn may be near the root of the placental subtree. Thus, while casting doubt on some recent conclusions, the analyses are also unveiling some interesting new possibilities.