Directional selection imposed by environmental variation can reduce intraspecific gene flow and promote population divergence. This is especially true if selection acts on traits with large fitness effect, for example, metabolic pathways. Mitochondrial and nuclear genetic structures over much of the species range of an Australian bird, the Eastern yellow robin (Eopsaltria australis), are perpendicular in space.  This is inferred to be the result of strong natural selection mainly in females affecting one or more of: mitochondrial genes, W-chromosome genes, other nuclear genes or interactions among these, notably mitochondrial-nuclear interactions. Given that mtDNA variation in this species is strongly correlated with hottest summer temperatures, we hypothesize that selection has acted on the Oxidative Phosphorylation (OXPHOS) pathway to energy production that is co-encoded by mitochondrial and nuclear genes. As starting point in testing this, we have analysed patterns of purifying and positive selection in complete mitochondrial genomes of two sister species of yellow robins, E. australis and E. griseogularis, and outgroups, focussing on the 13 mitochondrial-genes coding for OXPHOS proteins. Analysis of patterns of amino acid replacements, including changes in their physicochemical properties and projected protein structure, revealed that some regions of the E. australis mitogenome may have been shaped by positive selection, and this has potentially impacted protein functioning (i.e. may be locally adapted). These results contribute important information to testing for co-adaptive evolution of mitochondrial and nuclear genomes, for which genomic variation in nuclear-encoded OXPHOS genes will be collected across environmental transects.