Theory predicts that parallel evolution should be common when the number of beneficial mutations is limited by selective constraints on protein structure. However, confirmation is scarce in natural populations. Here we studied the major haemoglobin genes of eight Andean duck lineages and compared them to 115 other waterfowl species, including the bar-headed goose (Anser indicus) and Abyssinian blue-winged goose (Cyanochen cyanopterus), two additional species living at high altitude. One to five amino acid replacements were significantly overrepresented or derived in each highland population, and parallel substitutions were more common than in simulated sequences evolved under a neutral model. Two substitutions evolved in parallel in the alpha A subunit of two (Ala-alpha 8) and five (Thr-alpha 77) taxa, and five identical beta A subunit substitutions were observed in two (Ser-beta 4, Glu-beta 94, Met-beta 133) or three (Ser-beta 13, Ser-beta 116) taxa. Substitutions at adjacent sites within the same functional protein region were also observed. Five such replacements were in exterior, solvent-accessible positions on the A helix and AB corner of the alpha A subunit. Five others were in close proximity to inositolpentaphosphate binding sites, and two pairs of independent replacements occurred at two different alpha(1)beta(1) intersubunit contacts. More than half of the substitutions in highland lineages resulted in the acquisition of serine or threonine (18 gains vs. 2 losses), both of which possess a hydroxyl group that can hydrogen bond to a variety of polar substrates. The patterns of parallel evolution observed in these waterfowl suggest that adaptation to high-altitude hypoxia has resulted from selection on unique but overlapping sets of one to five amino acid substitutions in each lineage.