Antarctic icefish are extraordinary in their ability to thrive without haemoglobin. We wanted to understand how the mitochondrial proteome has adapted to the loss of this protein. Metabolic pathways that utilise oxygen are most likely to be rearranged in these species. Here, we have defined the mitochondrial proteomes of both the red and white muscle of two different icefish species (Champsocephalus gunnari and Chionodraco rastrospinosus) and compared these with two related red-blooded Notothenioids (Notothenia rossii, Trematomus bernacchii). Liquid Chromatography-Mass spectrometry (LC-MS/MS) was used to generate and examine the proteomic profiles of the two groups. We recorded a total of 91 differentially expressed proteins in the icefish red muscle mitochondria and 89 in the white muscle mitochondria when compared with the red-blooded related species. The icefish have a relatively higher abundance of proteins involved with Complex V of oxidative phosphorylation, RNA metabolism, and homeostasis, and fewer proteins for striated muscle contraction, haem, iron, creatine, and carbohydrate metabolism. Enrichment analyses showed that many important pathways were different in both red muscle and white muscle, including the citric acid cycle, ribosome machinery and fatty acid degradation. Life in the Antarctic waters poses extra challenges to the organisms that reside within them. Icefish have successfully inhabited this environment and we surmise that species without haemoglobin uniquely maintain their physiology. Our study highlights the mitochondrial protein pathway differences between similar fish species according to their specific tissue oxygenation idiosyncrasies.