Hemerythrins and hemocyanins are respiratory proteins present in some of the most ecologically diverse animal lineages; however, the precise evolutionary history of their enzymatic domains (hemerythrin, hemocyanin M, and tyrosinase) is still not well understood. We survey a wide dataset of prokaryote and eukaryote genomes and RNAseq data to reconstruct the phylogenetic origins of these proteins. We identify new species with hemerythrin, hemocyanin M, and tyrosinase domains in their genomes, particularly within animals, and demonstrate that the current distribution of respiratory proteins is due to several events of lateral gene transfer and/or massive gene loss. We conclude that the last common metazoan ancestor had at least two hemerythrin domains, one hemocyanin M domain, and six tyrosinase domains. The patchy distribution of these proteins among animal lineages can be partially explained by physiological adaptations, making these genes good targets for investigations into the interplay between genomic evolution and physiological constraints.