Introduction: Proteases play an important role in tumor progression. The predictive efficacy of proteases PRSS3 and PRSS22 mRNA levels for predicting relapse in surgically treated colon cancer (CC) patients was assessed. Methods: mRNA expression was quantified in 371 half lymph nodes (LNs) from 121 CC patients, 77 control LNs (13 patients), 66 primary colon tumors, and 30 normal colon tissues of these patients. Patients were also stratified according to their CEA mRNA level. The occurrence of relapse following curative surgery was evaluated using the Cox regression and Kaplan-Meier survival model analyses. Protein expression was examined through immunohistochemistry. Results: PRSS22 was superior to PRSS3 in identifying patients at risk of recurrence. Thus, high PRSS22 levels in LNs identified 76.5% of those who recurred, while PRSS3 only identified 17.6% of these patients and these were in TNM stages III and IV. The Kaplan-Meier analysis indicated that CC patients exhibiting elevated PRSS22 levels in lymph nodes experienced a reduction in survival time, averaging 37 months over the follow-up period (p = 0.009) and a 3-fold increased hazard risk (1.3–6.0; p = 0.01). In the group with low PRSS22 levels, only one patient experienced relapse at the 12-year follow-up when CEA mRNA analysis was included. A fraction of CEA-positive tumor cells expressed PRSS22 protein. Conclusion: The importance of the secreted serine protease, S1 family member PRSS22 in tumor progression is highlighted. It shows promise as a biomarker for CC prognosis and as a target to prevent tumor spread by inhibiting its enzymatic activity.