The progression of many solid tumors is characterized by the release of tumor-associated proteases, such as cancer procoagulant, MMP2 and MMP7. Consequently, the detection of tumor-specific proteolytic activity in serum specimens has recently been proposed as a new diagnostic tool in oncology. However, tumor-associated proteases are highly diluted in serum specimens and it is challenging to identify substrates that are specifically cleaved. In this study, we describe the systematic optimization of a synthetic peptide substrate using a positional scanning synthetic combinatorial library (PS-SCL) approach. The initial reporter peptide (RP) comprises of the cleavage site, WKPYDAAD, that is part of the coagulation factor X, the natural substrate of the tumor-associated cysteine protease cancer procoagulant (EC 3.4.22.26). Specifically, the amino acid substitution of aspartatic acid (D) in position P1' against asparagine (N) improved the processing of respective RPs in serum specimens from patients with colorectal tumors compared to healthy controls. Proteolytic fragments of RPs accumulated during prolonged incubation with serum specimens and were quantified with matrix-assisted laser desorption/ionization time-of-flight mass spectrometry. Finally, the optimized RP with the cleaved motif WKPYNAAD was combined with the RPs, VPLSLTMG and IPVSLRSG, that were cleaved by the tumor-associated proteases, MMP2 and MMP7, respectively. The diagnostic accuracy of MS-based protease profiling was evaluated for this triplex RP mix in a cohort of 50 serum specimens equally divided into colorectal cancer patients and healthy control individuals. Multiparametric analysis showed an AUC value of 0.90 for the receiver operating characteristic curve and was superior to the classification accuracy of the single markers. Our results demonstrate that RPs for MS-based protease profiling can systematically be optimized with a PS-SCL. Furthermore, the combination of different RPs can additionally increase the classification accuracy of functional protease profiling, and this in turn could lead to improved diagnosis, monitoring and prognosis of malignant disease.