High structural and sequence similarity within protein families can pose significant challenges to the development of selective inhibitors, especially toward proteolytic enzymes. Such enzymes usually belong to large families of closely similar proteases and may also hydrolyze, with different rates, protein- or peptide-based inhibitors. To address this challenge, we employed a combinatorial yeast surface display library approach complemented with a novel pre-equilibrium, competitive screening strategy for facile assessment of the effects of multiple mutations on inhibitor association rates and binding specificity. As a proof of principle for this combined approach, we utilized this strategy to alter inhibitor/protease association rates and to tailor the selectivity of the amyloid β-protein precursor Kunitz protease inhibitor domain (APPI) for inhibition of the oncogenic protease mesotrypsin, in the presence of three competing serine proteases, anionic trypsin, cationic trypsin and kallikrein-6. We generated a variant, designated APPIP13W/M17G/I18F/F34V, with up to 30-fold greater specificity relative to the parental APPIM17G/I18F/F34V protein, and 6500- to 230 000-fold improved specificity relative to the wild-type APPI protein in the presence of the other proteases tested. A series of molecular docking simulations suggested a mechanism of interaction that supported the biochemical results. These simulations predicted that the selectivity and specificity are affected by the interaction of the mutated APPI residues with nonconserved enzyme residues located in or near the binding site. Our strategy will facilitate a better understanding of the binding landscape of multispecific proteins and will pave the way for design of new drugs and diagnostic tools targeting proteases and other proteins.