Antarctic fish belonging to Notothenioidei represent an extraordinary example of radiation in the cold. In addition to the absence of hemoglobin, icefish show a number of other striking peculiarities including large-diameter blood vessels, high vascular densities, mitochondriarich muscle cells, and unusual mitochondrial architecture. In order to investigate the bases of icefish adaptation to the extreme Southern Ocean conditions we sequenced the complete genome of the icefish Chionodraco myersi. Comparative analyses of the icefish genome with those of other teleost species, including two additional white-blooded and five red-blooded notothenioids, provided a new perspective on the evolutionary loss of globin genes. Muscle transcriptome comparative analyses against red-blooded notothenioids as well as temperate fish revealed the peculiar regulation of genes involved in mitochondrial function in icefish. Gene duplication and promoter sequence divergence were identified as genome-wide patterns that likely contributed to the broad transcriptional program underlying the unique features of icefish mitochondria.