Identification of early cancer, detection of progression, and monitoring of therapeutic success remain urgent issues in clinical medicine, particularly given the increasing cancer incidence in our aging populations. New methodologies have provided enormous progress over the past decades by defining the genetic and proteomic composition of cancers, yielding putative cancer biomarkers detectable in blood or other body fluids less invasively and more cheaply than using currently available screening techniques that often involve biopsies or surgery. However, the clinical use of these new methodologies is still far off. In this review, we focus on putative soluble cancer biomarkers shed from the cell surface by metalloproteases overexpressed in numerous cancers. Although useful candidates have been identified, their validation and adoption into clinical use remain challenging.