RNA viruses are characterized by a high mutation rate, a buffer against environmental change. Nevertheless, the means by which random mutation improves viral fitness is not well characterized. Here we report the X-ray crystal structure of the receptor-binding domain (RBD) of the human coronavirus, HCoV-229E, in complex with the ectodomain of its receptor, aminopeptidase N (APN). Three extended loops are solely responsible for receptor binding and the evolution of HCoV-229E and its close relatives is accompanied by changing loop-receptor interactions. Phylogenetic analysis shows that the natural HCoV-229E receptor-binding loop variation observed defines six RBD classes whose viruses have successively replaced each other in the human population over the past 50 years. These RBD classes differ in their affinity for APN and their ability to bind an HCoV-229E neutralizing antibody. Together, our results provide a model for alphacoronavirus adaptation and evolution based on the use of extended loops for receptor binding.