To discover promising sulfated allosteric modulators (SAMs) of glycosaminoglycan-binding proteins (GBPs), such as human factor XIa (FXIa), we screened a library of 26 synthetic, sulfated quinazolin-4(3H)-ones (QAOs) resulting in the identification of six molecules that reduced the Vmax of substrate hydrolysis without influencing the KM. Mutagenesis of residues of the heparin-binding site (HBS) of FXIa introduced a nearly 5-fold loss in inhibition potency supporting recognition of an allosteric site. Fluorescence studies showed a sigmoidal binding profile indicating highly cooperative binding. Competition with a positively charged, heparin-binding polymer did not fully nullify inhibition suggesting importance of hydrophobic forces to binding. This discovery suggests the operation of a dual-element recognition process, which relies on an initial Coulombic attraction of anionic SAMs to the cationic HBS of FXIa that forms a locked complex through tight interaction with an adjacent hydrophobic patch. The dual-element strategy may be widely applicable for discovering SAMs of other GBPs.