Cytoglobin is a recently discovered myoglobin-related O2-binding protein of vertebrates with uncertain function. It occurs as single-copy gene in mammals. Here, we demonstrate the presence of two paralogous cytoglobin genes (Cygb-1 and Cygb-2) in the teleost fishes Danio rerio, Oryzias latipes, Tetraodon nigroviridis, and Takifugu rubripes. The globin-typical introns at positions B12.2 and G7.0 are conserved in both genes, whereas the C-terminal exon found in mammalian cytoglobin is absent in the fish genes. Phylogenetic analyses show that the two cytoglobin genes diverged early in teleost evolution. This is confirmed by gene synteny analyses, which suggest a large-scale duplication event. Although both cytoglobin genes are highly conserved and have evolved under purifying selection, substitution rates are significantly higher in Cygb-1 than in Cygb-2. Similar to their mammalian ortholog, both fish cytoglobins are expressed in a broad range of tissues. However, Cygb-2 is more than 250-fold stronger expressed in neuronal tissues, suggesting a subfunctionalization of the two cytoglobin paralogs after gene duplication.