Crescent-shaped red blood cells, the hallmark of sickle-cell disease, present a striking departure from the biconcave disc shape normally found in mammals. Characterized by increased mechanical fragility, sickled cells promote haemolytic anaemia and vaso-occlusions and contribute directly to disease in humans. Remarkably, a similar sickle-shaped morphology has been observed in erythrocytes from several deer species, without obvious pathological consequences. The genetic basis of erythrocyte sickling in deer, however, remains unknown. Here, we determine the sequences of human β-globin orthologues in 15 deer species and use protein structural modelling to identify a sickling mechanism distinct from the human disease, coordinated by a derived valine (E22V) that is unique to sickling deer. Evidence for long-term maintenance of a trans-species sickling/non-sickling polymorphism suggests that sickling in deer is adaptive. Our results have implications for understanding the ecological regimes and molecular architectures that have promoted convergent evolution of sickling erythrocytes across vertebrates.