Given the unique thermal history of the Antarctic continent, fishes of dominant suborder Notothenioidei offer a remarkable opportunity to study the physiological and biochemical characters gained and, conversely, lost during their evolutionary history and to map this information on the species phylogenetic trees. The availability of phylogenetically related notothenioid taxa living in a wide range of latitudes (in the Antarctic, sub-Antarctic and temperate regions) allows to look into the molecular bases of environmentally driven gene birth and death. This evolutionary perspective has also been supported by comparison of some features of the hemoprotein devoted to the oxygen transport in fish species living in the other polar region, the Arctic. The Arctic and Antarctic marine ichthyofaunas differ by age and isolation. Fishes of the two polar regions have undergone different regional histories which have engineered the physiological diversities, so that Antarctic fish are much more stenothermal than Arctic ones. Understanding the mechanisms of phenotypic response to cold exposure in species living at different latitudes in polar habitats offers fundamental insights into environmental adaptations. This review aims at surveying the current knowledge of molecular structure, functional features, phylogeny and adaptations of the hemoglobin of fish thriving in the Antarctic, sub-Antarctic and Arctic regions (with some excursions in the temperate latitudes). Investigating the evolutionary adaptations of hemoglobins to these environments can provide new insights into adaptation currently studied merely in temperate organisms, and can shed light into the convergent processes that evolved in response to thermal adaptations.