Cathepsin K, a lysosomal papain-like cysteine protease, forms collagenolytically highly active complexes with chondroitin sulfate and represents the most potent mammalian collagenase. Here we demonstrate that complex formation with glycosaminoglycans (GAGs) is unique for cathepsin K among human papain-like cysteine proteases and that different GAGs compete for the binding to cathepsin K. GAGs predominantly expressed in bone and cartilage, such as chondroitin and keratan sulfates, enhance the collagenolytic activity of cathepsin K, whereas dermatan, heparan sulfate, and heparin selectively inhibit this activity. Moreover, GAGs potently inhibit the collagenase activity of other cysteine proteases such as cathepsins L and S at 37 °C. Along this line MMP1-generated collagen fragments in the presence of GAGs are stable against further degradation at 28 °C by all cathepsins but cathepsin K, whereas thermal destabilization at 37 °C renders the fragments accessible to all cathepsins. These results suggest a novel mechanism for the regulation of matrix protein degradation by GAGs. It further implies that cathepsin K represents the only lysosomal collagenolytic activity under physiologically relevant conditions.