As avian influenza A(H5N1) viruses continue to circulate in Asia and Africa, global concerns of an imminent pandemic persist. Recent experimental studies suggest that efficient transmission between humans of current H5N1 viruses only requires a few genetic changes. An essential step is alteration of the virus hemagglutinin from preferential binding to avian receptors for the recognition of human receptors present in the upper airway. We have identified receptor-binding changes which emerged during H5N1 infection of humans, due to single amino acid substitutions, Ala134Val and Ile151Phe, in the hemagglutinin. Detailed biological, receptor-binding, and structural analyses revealed reduced binding of the mutated viruses to avian-like receptors, but without commensurate increased binding to the human-like receptors investigated, possibly reflecting a receptor-binding phenotype intermediate in adaptation to more human-like characteristics. These observations emphasize that evolution in nature of avian H5N1 viruses to efficient binding of human receptors is a complex multistep process.