Neuroglobin and cytoglobin are two novel members of the vertebrate globin family. Their physiological role is poorly understood, although both proteins bind oxygen reversibly and may be involved in cellular oxygen homeostasis. Here we investigate the selective constraints on coding and non-coding sequences of the neuroglobin and cytoglobin genes in human, mouse, rat and fish. Neuroglobin and cytoglobin are highly conserved, displaying very low levels of non-synonymous nucleotide substitutions. An oxygen supply function predicts distinct modes of gene regulation, involving hypoxia-responsive transcription factors. To detect conserved candidate regulatory elements, we compared the neuroglobin and cytoglobin genes in mammals and fish. The myoglobin gene was included to test if it also contains hypoxia-responsive regulatory elements. Long conserved non-coding sequences, indicative of gene-regulatory elements, were found in the cytoglobin and myoglobin, but not in the neuroglobin gene. Sequence comparison and experimental data allowed us to delimit upstream regions of the neuroglobin and cytoglobin genes that contain the putative promoters, defining candidate regulatory regions for functional tests. The neuroglobin and the myoglobin genes both lack conserved hypoxia-responsive elements (HREs) for transcriptional activation, but contain conserved hypoxia-inducible mRNA stabilization signals in their 3′ untranslated regions. The cytoglobin gene, in contrast, harbors both conserved HREs and mRNA stabilization sites, strongly suggestive of an oxygen-dependent regulation.