The hemagglutinin-esterases (HEs), envelope glycoproteins of corona-, toro- and orthomyxoviruses, mediate reversible virion attachment to O-acetylated sialic acids (O-Ac-Sias). They do so through concerted action of distinct receptor-binding ("lectin") and receptor-destroying sialate O-acetylesterase ("esterase") domains. Most HEs target 9-O-acetylated Sias. In one lineage of murine coronaviruses, however, HE esterase substrate and lectin ligand specificity changed dramatically as these viruses evolved to use 4-O-acetylated Sias instead. Here we present the crystal structure of the lectin domain of mouse hepatitis virus (MHV) strain S HE, resolved both in its native state and in complex with a receptor analogue. The data show that the shift from 9-O- to 4-O-Ac-Sia receptor usage primarily entailed a change in ligand binding topology and, surprisingly, only modest changes in receptor-binding site architecture. Our findings illustrate the ease with which viruses can change receptor-binding specificity with potential consequences for host-, organ and/or cell tropism, and for pathogenesis.