Bone resorption in balance with bone formation is vital for the maintenance of the skeleton and is mediated by osteoclasts. Cathepsin K is the predominant protease in osteoclasts that degrades the bulk of the major bone forming organic component, type I collagen. Although the potent collagenase activity of cathepsin K is well known, its mechanism of action remains elusive. Here, we report a cathepsin K-specific complex with chondroitin sulfate, which is essential for the collagenolytic activity of the enzyme. The complex is an oligomer consisting of five cathepsin K and five chondroitin sulfate molecules. Only the complex exhibits potent triple helical collagen-degrading activity, whereas monomeric cathepsin K has no collagenase activity. The primary substrate specificity of cathepsin K is not altered by complex formation, suggesting that the protease-chondroitin sulfate complex primarily facilitates the destabilization and/or the specific binding of the triple helical collagen structure. Inhibition of complex formation leads to the loss of collagenolytic activity but does not impair the proteolytic activity of cathepsin K toward noncollagenous substrates. The physiological relevance of cathepsin K complexes is supported by the findings that (i) the content of chondroitin sulfate present in bone and accessible to cathepsin K activity is sufficient for complex formation and (ii) Y212C, a cathepsin K mutant that causes pycnodysostosis (a bone sclerosing disorder) and that has no collagenase activity but remains potent as a gelatinase, is unable to form complexes. These findings reveal a novel mechanism of bone collagen degradation and suggest that targeting cathepsin K complex formation would be an effective and specific treatment for diseases with excessive bone resorption such as osteoporosis.