Helicobacter pylori is associated with inflammatory diseases and can cause gastric cancer and mucosa-associated lymphoma. One of the bacterium's key proteins is high temperature requirement A (HpHtrA) protein, an extracellular serine protease that cleaves E-cadherin of gastric epithelial cells, which leads to loss of cell-cell adhesion. Inhibition of HpHtrA may constitute an intervention strategy against H. pylori infection. Guided by the computational prediction of hypothetical ligand binding sites on the surface of HpHtrA, we performed residue mutation experiments that confirmed the functional relevance of an allosteric region. We virtually screened for potential ligands addressing this surface cleft located between the catalytic and PDZ1 domains. Our receptor-based computational method represents protein surface pockets in terms of graph frameworks and retrieves small molecules that satisfy the constraints given by the pocket framework. A new chemical entity was identified that blocked E-cadherin cleavage in vitro by direct binding to HpHtrA, and efficiently blocked pathogen transmigration across the gastric epithelial barrier. A preliminary crystal structure of HpHtrA confirms the validity of a comparative "homology" model of the enzyme, which we used for the computational study. The results of this study demonstrate that addressing orphan protein surface cavities of target macromolecules can lead to new bioactive ligands.