Cytochrome c oxidase (COX) subunit 4 has two paralogs in most vertebrates. The mammalian COX4-2 gene is hypoxia responsive and the protein has a disrupted ATP-binding site that confers kinetic properties on COX that distinguish it from COX4-1. The structure -function of COX4-2 orthologs in other vertebrates remains uncertain. Phylogenetic analyses suggest the two paralogs arose in basal vertebrates, but COX4-2 orthologs diverged faster than COX4-1 orthologs. COX4-1/4-2 protein levels in tilapia tracked mRNA levels across tissues, and did not change in hypoxia, arguing against a role for differential post-translational regulation of paralogs. Heart, and to a lesser extent brain, showed a size-dependent shift from COX4-1 to COX4-2 (transcript and protein). ATP allosterically inhibited both velocity and affinity for oxygen in COX assayed from both muscle (predominately COX4-2) and gill (predominately COX4-1). We saw some evidence of cellular and subcellular discrimination of COX4 paralogs in heart. In cardiac ventricle, some non-cardiomyocyte cells were COX positive but lacked detectible COX4-2. Within heart, the two proteins partitioned to different mitochondrial subpopulations. Cardiac subsarcolemmal mitochondria had mostly COX4-1 and intermyofibrillar mitochondria had mostly COX4-2. Collectively, these data argue that despite common evolutionary origins, COX4-2 orthologs of fish show unique patterns of subfunctionalization with respect to transcriptional and post-translation regulation, relative to the rodents and primates that have been studied to date.