Cancer is responsible for many deaths and is a major source of healthcare expenditures. The identification of new, non-invasive biomarkers might allow improvement of the direct diagnostic or prognostic ability of already available tools. Here, we took the innovative approach of interrogating the activity of exopeptidases in the serum of cancer patients with the aim of establishing a distinction based on enzymatic function, instead of simple protein levels, as a means to biomarker discovery. We first analyzed two well-characterized mouse models of prostate cancer, each with a distinct genetic lesion, and established that broad exopeptidase and targeted aminopeptidase activity tests reveal proteolytic changes associated with tumor development. We also describe new peptide-based freeze-frame reagents uniquely suited to probe the altered balance of selected aminopeptidases, as opposed to the full array of exopeptidases, and/or their modulators in patient serum or plasma. One particular proteolytic activity was impaired in animals with aggressive disease relative to cancer-free littermates. We identified the protease in question as dipeptidyl peptidase 4 (DPP4) by analyzing selected knockout mice and evaluating the effect of specific inhibitors. DPP4 activity was also reduced in the sera of patients with metastatic prostate cancer relative to patients with localized disease or healthy controls. However, no significant differences in DPP4 serum levels were observed, which established the loss of activity as the result of impaired enzymatic function. Biochemical analysis indicated that reduced activity was the result not of post-translational modifications or allosteric changes, but instead of a low-molecular-weight inhibitor. After we adjusted for age and total prostate-specific antigen, reduced DPP4 activity remained a significant predictor of cancer status. The results of this proof-of-principle study suggest that DPP4 activity might be a potential blood-based indicator of the presence of metastatic cancer of prostatic origin, either by itself or, more likely, as a means to improve the sensitivity and specificity of existing markers.