The terminal enzyme of the mitochondrial respiratory chain, cytochrome oxidase, transfers electrons to molecular oxygen, generating water. Within the inner mitochondrial membrane, cytochrome oxidase assembles into supercomplexes, together with other respiratory chain complexes, forming so-called respirasomes. Little is known about how these higher oligomeric structures are attained. Here we report on Rcf1 and Rcf2 as cytochrome oxidase subunits in S. cerevisiae. While Rcf2 is specific to yeast, Rcf1 is a conserved subunit with two human orthologs, RCF1a and RCF1b. Rcf1 is required for growth in hypoxia and complex assembly of subunits Cox13 and Rcf2, as well as for the oligomerization of a subclass of cytochrome oxidase complexes into respirasomes. Our analyses reveal that the cytochrome oxidase of mitochondria displays intrinsic heterogeneity with regard to its subunit composition and that distinct forms of respirasomes can be formed by complex variants.