A series of secreted proteases are included among the virulence factors documented for Staphylococcus aureus. In light of increasing antibiotic resistance of this dangerous human pathogen, these proteases are considered as suitable targets for the development of novel therapeutic strategies. The recent discovery of staphostatins, endogenous, highly specific, staphylococcal cysteine protease inhibitors, opened a possibility for structure-based design of low molecular weight analogues. Moreover, the crystal structure of staphostatin B revealed a distinct folding pattern and an unexpected, substrate-like binding mode. The solution structure of staphostatin A reported here confirms that staphostatins constitute a novel, distinct class of cysteine protease inhibitors. In addition, the structure knowledge-based mutagenesis studies shed light on individual structural features of staphostatin A, the inhibition mechanism, and the determinants of distinct specificity of staphostatins toward their target proteases.