Hemoglobin and myoglobin are oxygen transport and storage proteins of most vertebrates. Neuroglobin (Ngb) and cytoglobin (Cygb)--two recent additions to the vertebrate globin superfamily--have still disputed functions. Combining the data from all available resources, we investigate the evolution of these novel globins. Both Ngb and Cygb show little sequence variation in vertebrate evolution, suggesting conserved structures and functions, and an important role in the animal's metabolism. Exon-intron patterns remained unchanged in Ngb and Cygb, with the exception of the addition of a 3' exon to Cygb early in mammalian evolution. In phylogenetic analyses, Ngb forms a common branch with globin X, another recently identified globin with undefined function in lower vertebrates, and with some invertebrate nerve globins. This shows an early divergence of this branch in animal evolution. Cygb is related to myoglobin, and associated with an eye-specific globin from birds. The pattern of globin evolution shows that proteins with clear respiratory roles evolved independently from intracellular globins with uncertain functions. This result suggests either multiple independent functional changes or a yet undefined respiratory role of tissue globins like Ngb and Cygb.