To investigate the predictability of genetic adaptation, we examined the molecular basis of convergence in hemoglobin function in comparisons involving 56 avian taxa that have contrasting altitudinal range limits. Convergent increases in hemoglobin-oxygen affinity were pervasive among high-altitude taxa, but few such changes were attributable to parallel amino acid substitutions at key residues. Thus, predictable changes in biochemical phenotype do not have a predictable molecular basis. Experiments involving resurrected ancestral proteins revealed that historical substitutions have context-dependent effects, indicating that possible adaptive solutions are contingent on prior history. Mutations that produce an adaptive change in one species may represent precluded possibilities in other species because of differences in genetic background.