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 pathological consequences. The genetic basis of erythrocyte sickling in deer, however, remains unknown, limiting the utility of deer as comparative models for sickling. Here, we determine the sequences of human β-globin orthologs in 15 deer species and identify a set of co-evolving, structurally related residues that distinguish sickling from non-sickling deer. Protein structural modelling indicates a sickling mechanism distinct from human sickle cell disease, coordinated by a derived valine (E22V) in the second alpha helix of the β-globin protein. The evolutionary history of deer β-globins is characterized by incomplete lineage sorting, episodes of gene conversion between adult and foetal β-globin paralogs, and the presence of a trans-species polymorphism that is best explained by long-term balancing selection, suggesting that sickling in deer is adaptive. Our results reveal structural and evolutionary parallels and differences in erythrocyte sickling between human and deer, with implications for understanding the ecological regimes and molecular architectures that favour the evolution of this dramatic change in erythrocyte shape.