Proteoglycans are major constituents of extracellular matrices, as well as cell surfaces and basement membranes. They play key roles in supporting the dynamic extracellular matrix by generating complex structural networks with other macromolecules and by regulating cellular phenotypes and signaling. It is becoming evident, however, that proteolytic enzymes are required partners for matrix remodeling and for modulating cell signaling via matrix constituents. Proteinases contribute to all stages of diseases, particularly cancer development and progression, and contextually participate in either the removal of damaged products or in the processing of matrix molecules and signaling receptors. The dynamic interplay between proteoglycans and proteolytic enzymes is a crucial biological step that contributes to the pathophysiology of cancer and inflammation. Moreover, proteoglycans are implicated in the expression and secretion of proteolytic enzymes and often modulate their activities. In this review, we describe the emerging biological roles of proteoglycans and proteinases, with a special emphasis on their complex interplay. We critically evaluate this important proteoglycan-proteinase interactome and discuss future challenges with respect to targeting this axis in the treatment of cancer.