The evolution of flight is the most important feature of birds, and this ability has helped them become one of the most successful groups of vertebrates. However some species have independently lost their ability to fly. The degeneration of flight ability is a long process, and some species remain transitional locomotive models. Most of the energy required for locomotion is supplied by mitochondria via oxidative phosphorylation. Thus, rapidly flying birds should require a more energy efficient metabolism than weakly flying or flightless species. Therefore, we speculated that evolutionary constraints acted on the mtDNA of birds with different locomotive abilities. To test this hypothesis, we compared 76 complete avian mitochondrial genomes. Weakly flying and flightless birds, compared to rapidly flying birds, accumulated more nonsynonymous nucleotide substitutions relative to synonymous substitutions. Even after controlling for mutation rate, this trend remained significant. This finding was further tested for its generality by examining 214 complete mammalian mitochondrial genomes. The same as birds, a negative correlation was also found for the Ka/Ks ratio and locomotive speed. Our results demonstrated that, in addition to the previously described role for effective population size, functional constraints due to locomotion play an important role in the evolution of mtDNA.