Natural selection often promotes evolutionary innovation by coopting preexisting genes for new functions, and this process may be greatly facilitated by gene duplication. Here we report an example of cooptive convergence where paralogous members of the globin gene superfamily independently evolved a specialized O(2) transport function in the two deepest branches of the vertebrate family tree. Specifically, phylogenetic evidence demonstrates that erythroid-specific O(2) transport hemoglobins evolved independently from different ancestral precursor proteins in jawed vertebrates (gnathostomes) and jawless fish (cyclostomes, represented by lamprey and hagfish). A comprehensive phylogenetic analysis of the vertebrate globin gene superfamily revealed that the erythroid hemoglobins of cyclostomes are orthologous to the cytoglobin protein of gnathostome vertebrates, a hexacoordinate globin that has no O(2) transport function and that is predominantly expressed in fibroblasts and related cell types. The phylogeny reconstruction also revealed that vertebrate-specific globins are grouped into four main clades: (i) cyclostome hemoglobin + cytoglobin, (ii) myoglobin + globin E, (iii) globin Y, and (iv) the alpha- and beta-chain hemoglobins of gnathostomes. In the hemoglobins of gnathostomes and cyclostomes, multisubunit quaternary structures provide the basis for cooperative O(2) binding and allosteric regulation by coupling the effects of ligand binding at individual subunits with interactions between subunits. However, differences in numerous structural details belie their independent origins. This example of convergent evolution of protein function provides an impressive demonstration of the ability of natural selection to cobble together complex design solutions by tinkering with different variations of the same basic protein scaffold.