Staphostatins constitute a family of staphylococcal cysteine protease inhibitors sharing a lipocalin-like fold and a unique mechanism of action. Each of these cytoplasmic proteins is co-expressed from one operon, together with a corresponding target extracellular cysteine protease (staphopain). To cast more light on staphostatin/staphopain interaction and the evolution of the encoding operons, we have cloned and characterized a staphopain (StpA2aur CH-91) and its inhibitor (StpinA2aur CH-91) from a novel staphylococcal thiol protease operon (stpAB2CH-91) identified in S. aureus strain CH-91. Furthermore, we have expressed a staphostatin from Staphylococcus warneri (StpinBwar) and characterized its target protease (StpBwar). Analysis of the reciprocal interactions among novel and previously described members of the staphostatin and staphopain families demonstrates that the co-transcribed protease is the primary target for each staphostatin. Nevertheless, the inhibitor derived from one species of Staphylococcus can inhibit the staphopain from another species, although the Ki values are generally higher and inhibition only occurs if both proteins belong to the same subgroup of either S. aureus staphopain A/staphostatin A (alpha group) or staphopain B/staphostatin B (beta group) orthologs. This indicates that both subgroups arose in a single event of ancestral allelic duplication, followed by parallel evolution of the protease/inhibitor pairs. The tight coevolution is likely the result of the known deleterious effects of uncontrolled staphopain action.