The highly contagious measles virus infects millions of individuals worldwide, causing serious disease in children of developing countries. Infection is initiated by attachment of the measles virus hemagglutinin (MV-H), a glycoprotein anchored to the virus envelope, to the host cell receptors CD46 or signaling lymphocyte activation molecule (SLAM). Here we report the crystal structure of MV-H in complex with a CD46 protein spanning the two N-terminal domains. A unique groove at the side of the MV-H beta-propeller domain, which is absent in homologous paramyxovirus attachment proteins, engages residues in both CD46 domains. Key contacts involve a protruding loop in the N-terminal CD46 domain that carries two sequential proline residues (PP motif) and penetrates deeply into a hydrophobic socket in MV-H. We identify a similar PP motif in SLAM, defining a common measles virus recognition epitope in the CD46 and SLAM receptor proteins.