Myoglobin (Mb) is the classic vertebrate oxygen-binding protein present in aerobic striated muscles. It functions principally in oxygen delivery and provides muscle with its characteristic red colour. Members of the Antarctic icefish family (Channichthyidae) are widely thought to be extraordinary for lacking cardiac Mb expression, a fact that has been attributed to their low metabolic rate and unusual evolutionary history. Here, we report that cardiac Mb deficit, associated with pale heart colour, has evolved repeatedly during teleost evolution. This trait affects both gill- and air-breathing species from temperate to tropical habitats across a full range of salinities. Cardiac Mb deficit results from total pseudogenization in three-spined stickleback and is associated with a massive reduction in mRNA level in two species that evidently retain functional Mb. The results suggest that near or complete absence of Mb-assisted oxygen delivery to heart muscle is a common facet of teleost biodiversity, even affecting lineages with notable oxygen demands. We suggest that Mb deficit may affect how different teleost species deal with increased tissue oxygen demands arising under climate change.