The migration of the human pathogen Streptococcus pyogenes (group A streptococcus) from localized to deep tissue sites may result in severe invasive disease, and sequestration of the host zymogen plasminogen appears crucial for virulence. Here, we describe a novel plasminogen-binding M protein, the plasminogen-binding group A streptococcal M protein (PAM)-related protein (Prp). Prp is phylogenetically distinct from previously described plasminogen-binding M proteins of group A, C, and G streptococci. While competition experiments indicate that Prp binds plasminogen with a lower affinity than PAM (50% effective concentration = 0.34 µM), Prp nonetheless binds plasminogen with high affinity and at physiologically relevant concentrations of plasminogen (Kd = 7.8 nM). Site-directed mutagenesis of the putative plasminogen binding site indicates that unlike the majority of plasminogen receptors, Prp does not interact with plasminogen exclusively via lysine residues. Mutagenesis to alanine of lysine residues Lys96 and Lys101 reduced but did not abrogate plasminogen binding by Prp. Plasminogen binding was abolished only with the additional mutagenesis of Arg107 and His108 to alanine. Furthermore, mutagenesis of Arg107 and His108 abolished plasminogen binding by Prp despite the presence of Lys96 and Lys101 in the binding site. Thus, binding to plasminogen via arginine and histidine residues appears to be a conserved mechanism among plasminogen-binding M proteins.