A major challenge in evolutionary biology is to identify the genes underlying adaptation. The oxygen-transporting haemoglobins directly link external conditions with metabolic needs and therefore represent a unique system for studying environmental effects on molecular evolution. We have discovered two haemoglobin polymorphisms in Atlantic cod populations inhabiting varying temperature and oxygen regimes in the North Atlantic. Three-dimensional modelling of the tetrameric haemoglobin structure demonstrated that the two amino acid replacements Met55beta1Val and Lys62beta1Ala are located at crucial positions of the alpha1beta1 subunit interface and haem pocket, respectively. The replacements are proposed to affect the oxygen-binding properties by modifying the haemoglobin quaternary structure and electrostatic feature. Intriguingly, the same molecular mechanism for facilitating oxygen binding is found in avian species adapted to high altitudes, illustrating convergent evolution in water- and air-breathing vertebrates to reduction in environmental oxygen availability. Cod populations inhabiting the cold Arctic waters and the low-oxygen Baltic Sea seem well adapted to these conditions by possessing the high oxygen affinity Val55-Ala62 haplotype, while the temperature-insensitive Met55-Lys62 haplotype predominates in the southern populations. The distinct distributions of the functionally different haemoglobin variants indicate that the present biogeography of this ecologically and economically important species might be seriously affected by global warming.