In a wide range of taxa, proteins encoded by mitochondrial genomes are involved in adaptation to lifestyle that requires oxygen starvation or elevation of metabolism rate. It remains poorly understood to what extent adaptation to similar conditions is associated with parallel changes in these proteins. We search for a genetic signal of parallel or convergent evolution in recurrent molecular adaptation to high altitude, migration, diving, wintering, unusual flight abilities, or loss of flight in mitochondrial genomes of birds. Developing on previous work, we design an approach for the detection of recurrent coincident changes in genotype and phenotype, indicative of an association between the two. We describe a number of candidate sites involved in recurrent adaptation in ND genes. However, we find that the majority of convergence events can be explained by random coincidences without invoking adaptation.