Vertebrate life originated in the aquatic environment and many fundamental red blood cell (RBC) characteristics evolved in the fish lineage. This chapter describes how RBC morphology, hemoglobin (Hb), carbonic anhydrase (CA), anion exchangers (AE), membrane transport pathways, sensing and signaling mechanisms have changed throughout the evolution of fishes, from the basal agnathans, to the derived teleosts. The RBCs of all fishes are nucleated and transcriptionally active, have mitochondria and a highly aerobic metabolism. Hagfishes, the most basal extant vertebrates, express monomeric Hbs in large RBCs without AE, volume or pH regulation. While lamprey also lack RBC AE, their RBCs control volume and pH, and express monomeric Hbs that have convergently evolved mechanisms of cooperativity and pH-sensitivity. The basal gnathostomes, sharks and rays, gave rise to RBC AE activity and tetrameric Hbs that are modulated by organic phosphates. In the teleost fishes that represent half of all vertebrates, extremely pH-sensitive Hbs are acidified in specialized vascular structures in the eyes and the swim bladder to unload oxygen (O2) at several hundred atmospheres of pressure. During a systemic acidosis, adrenergic stimulation activates membrane transporters in teleost RBCs that protect pH and Hb-O2 binding. These transporters interact with plasma-accessible CA in the vasculature to promote O2 unloading at the tissues of teleosts, which is essential to support maximal exercise performance. Finally, Antarctic icefishes, a derived group of extremophile teleosts, do not express Hb and have largely lost RBCs from the circulation, resulting in extreme cardio-respiratory phenotypes that offer unique opportunities for fundamental physiology research.