No vaccine exists against group A Streptococcus (GAS), a leading cause of worldwide morbidity and mortality. A severe hurdle is the hypervariability of its major antigen, the M protein, with >200 different M types known. Neutralizing antibodies typically recognize M protein hypervariable regions (HVRs) and confer narrow protection. In stark contrast, human C4b-binding protein (C4BP), which is recruited to the GAS surface to block phagocytic killing, interacts with a remarkably large number of M protein HVRs (apparently ∼90%). Such broad recognition is rare, and we discovered a unique mechanism for this through the structure determination of four sequence-diverse M proteins in complexes with C4BP. The structures revealed a uniform and tolerant 'reading head' in C4BP, which detected conserved sequence patterns hidden within hypervariability. Our results open up possibilities for rational therapies that target the M-C4BP interaction, and also inform a path towards vaccine design.