By using complete sequence data of mitochondrial DNAs, three Markov models (Dayhoff, Proportional, and Poisson models) for amino acid substitutions during evolution were applied in maximum likelihood analyses of mitochondrially encoded proteins to estimate a phylogenetic tree depicting human, cow, whale, and murids (mouse and rat), with chicken, frog, and carp as outgroups. A cow/whale clade was confirmed with a more than 99.8% confidence level by any of the three models, but the branching order among human, murids, and the cow/whale clade remained uncertain. It turned out that the Dayhoff model is by far the most appropriate model among the alternatives in approximating the amino acid substitutions of mitochondrially encoded proteins, which is consistent with a previous analysis of a more limited data set. It was shown that the substitution rate of mitochondrially encoded proteins has increased in the order of fishes, amphibians, birds, and mammals and that the rate in mammals is at least six times, probably an order of magnitude, higher than that in fishes. The higher evolutionary rate in birds and mammals than in amphibians and fishes was attributed to relaxation of selective constraints operating on proteins in warm-blooded vertebrates and to high mutation rate of bird and mammalian mitochondrial DNAs.