A survey of genomes for the presence of gene clusters related to cbb3 oxidases detected bona fide members of the family in almost all phyla of the domain Bacteria. No archaeal representatives were found. The subunit composition was seen to vary substantially between clades observed on the phylogenetic tree of the catalytic subunit CcoN. The protein diade formed by CcoN and the monoheme cytochrome CcoO appears to constitute the functionally essential “core” of the enzyme conserved in all sampled cbb3 gene clusters. The topology of the phylogenetic tree contradicts the scenario of a recent origin of cbb3 oxidases and substantiates the status of this family as a phylogenetic entity on the same level as the other subgroups of the heme-copper superfamily (including nitric oxide reductase). This finding resuscitates and exacerbates the conundrum of the evolutionary origin of heme-copper oxidases.