Protease substrate profiling has nowadays almost become a routine task for experimentalists, and the knowledge on protease peptide substrates is easily accessible via the MEROPS database. We present a shape-based virtual screening workflow using vROCS that applies the information about the specificity of the proteases to find new small-molecule inhibitors. Peptide substrate sequences for three to four substrate positions of each substrate from the MEROPS database were used to build the training set. Two-dimensional substrate sequences were converted to three-dimensional conformations through mutation of a template peptide substrate. The vROCS query was built from single amino acid queries for each substrate position considering the relative frequencies of the amino acids. The peptide-substrate-based shape-based virtual screening approach gives good performance for the four proteases thrombin, factor Xa, factor VIIa, and caspase-3 with the DUD-E data set. The results show that the method works for protease targets with different specificity profiles as well as for targets with different active-site mechanisms. As no structure of the target and no information on small-molecule inhibitors are required to use our approach, the method has significant advantages in comparison with conventional structure- and ligand-based methods.