Influenza A viruses (IAV) initiate infection by binding to glycans with terminal sialic acids on the cell surface. Hosts of IAV variably express two major forms of sialic acid, N-acetylneuraminic acid (NeuAc) and N-glycolylneuraminic acid (NeuGc). NeuGc is produced in most mammals including horses and pigs, but is absent in humans, ferrets, and birds. The only known naturally occurring IAVs that exclusively bind NeuGc are extinct highly pathogenic equine H7N7 viruses. We determined the crystal structure of a representative equine H7 hemagglutinin (HA) in complex with NeuGc and observed high similarity in the receptor-binding domain with an avian H7 HA. To determine the molecular basis for NeuAc and NeuGc specificity, we performed systematic mutational analyses, based on the structural insights, on two distant avian H7 HAs and an H15 HA. We found that mutation A135E is key for binding α2,3-linked NeuGc but does not abolish NeuAc binding. Additional mutations S128T, I130V, T189A, and K193R converted the specificity from NeuAc to NeuGc. We investigated the residues at positions 128, 130, 135, 189, and 193 in a phylogenetic analysis of avian and equine H7 HAs. This revealed a clear distinction between equine and avian residues. The highest variability was observed at key position 135, of which only the equine glutamic acid led to NeuGc binding. These results demonstrate that genetically distinct H7 and H15 HAs can be switched from NeuAc to NeuGc binding and vice versa after introduction of several mutations, providing insights into the adaptation of H7 viruses to NeuGc receptors. (250 words) Importance Influenza A viruses cause millions of cases of severe illness and deaths annually. To initiate infection and replicate, the virus first needs to bind to a structure on the cell surface, like a key fitting in a lock. For influenza A viruses, these ´keys´ (receptors) on the cell surface are chains of sugar molecules (glycans). The terminal sugar on these glycans is often either N-acetylneuraminic acid (NeuAc) or N-glycolylneuraminic acid (NeuGc). Most influenza A viruses bind NeuAc, but a small minority binds NeuGc. NeuGc is present in species like horses, pigs, and mice, but not in humans, ferrets, and birds. Here, we investigated the molecular determinants of NeuGc specificity and the origin of viruses that bind NeuGc.