Mitochondrial genomes encode fundamental subunits of the basic energy producing machinery of eukaryotic cells that are under strong functional constraint. Paradoxically, these genes evolve rapidly in general, and there is substantial variation in evolutionary rates among genes within genomes. In order to investigate spatial variation in selection intensity, we conducted tests of neutrality using ratios of synonymous to nonsynonymous substitutions (dN/dS=ω) on numerous protein gene segments from fishes and mammals. Values of ω were very low for nearly all genomic regions. However, values of both ω and dN varied in a clinal pattern with increasing distance from the light-strand origin of replication. Spatial heterogeneity of nonsynonymous substitution rates exhibits a significantly positive correlation with variation in mutation rates that are related to the mode of mitochondrial DNA replication. The finding that nonsynonymous substitution rates are proportional to mutation rates is expected if a majority of substitutions are selectively neutral or slightly deleterious. Spatial patterns of among-gene variation in nonsynonymous rates were highly similar between fishes and mammals, suggesting that forces governing mitochondrial gene evolution have remained relatively constant over 450 Myr of vertebrate evolution. Conservation of substitution patterns despite major shifts in thermal habit and metabolic demands among taxa implicates a conserved replication mechanism controlling relative mutation rates as a major determinant of mitochondrial protein evolution.