Background Functionality of the tetrameric hemoglobin molecule seems to be determined by a few amino acids located in key positions. Oxygen binding encompasses structural changes at the interfaces between the α1β2 and α2β1 dimers, but also subunit interactions are important for the oxygen binding affinity and stability. The latter packing contacts include the conserved Arg B12 interacting with Phe GH5, which is replaced by Leu and Tyr in the αA and αD chains, respectively, of birds and reptiles. Results Searching all known hemoglobins from a variety of gnathostome species (jawed vertebrates) revealed the almost invariant Arg B12 coded by the AGG triplet positioned at an exon-intron boundary. Rare substitutions of Arg B12 in the gnathostome β globins were found in pig, tree shrew and scaled reptiles. Phe GH5 is also highly conserved in the β globins, except for the Leu replacement in the β1 globin of five marine gadoid species, gilthead seabream and the Comoran coelacanth, while Cys and Ile were found in burbot and yellow croaker, respectively. Atlantic cod β1 globin showed a Leu/Met polymorphism at position GH5 dominated by the Met variant in northwest-Atlantic populations that was rarely found in northeast-Atlantic cod. Site-specific analyses identified six consensus codons under positive selection, including 122β(GH5), indicating that the amino acid changes identified at this position may offer an adaptive advantage. In fact, computational mutation analysis showed that the replacement of Phe GH5 with Leu or Cys decreased the number of van der Waals contacts essentially in the deoxy form that probably causes a slight increase in the oxygen binding affinity. Conclusions The almost invariant Arg B12 and the AGG codon seem to be important for the packing contacts and pre-mRNA processing, respectively, but the rare mutations identified might be beneficial. The Leu122β1(GH5)Met and Met55β1(D6)Val polymorphisms in Atlantic cod hemoglobin modify the intradimer contacts B12-GH5 and H2-D6, while amino acid replacements at these positions in avian hemoglobin seem to be evolutionary adaptive in air-breathing vertebrates. The results support the theory that adaptive changes in hemoglobin functions are caused by a few substitutions at key positions.