Human cysteine cathepsin S (catS) participates in distinct physiological and pathophysiological cellular processes and is considered as a valuable therapeutic target in autoimmune diseases, cancer, atherosclerosis, and asthma. We evaluated the capacity of negatively charged glycosaminoglycans (heparin, heparan sulfate, chondroitin 4/6-sulfates, dermatan sulfate, and hyaluronic acid) to modulate the activity of catS. Chondroitin 4-sulfate (C4-S) impaired the collagenolytic activity (type IV collagen) and inhibited the peptidase activity (Z-Phe-Arg-AMC) of catS at pH 5.5, obeying a mixed-type mechanism (estimated Ki = 16.5 ± 6 μM). Addition of NaCl restored catS activity, supporting the idea that electrostatic interactions are primarly involved. Furthermore, C4-S delayed in a dose-dependent manner the maturation of procatS at pH 4.0 by interfering with the intermolecular processing pathway. Binding of C4-S to catS was demonstrated by gel-filtration chromatography, and its affinity was measured by surface plasmon resonance (equilibrium dissociation constant Kd = 210 ± 40 nM). Moreover, C4-S induced subtle conformational changes in mature catS as observed by intrinsic fluorescence spectroscopy analysis. Molecular docking predicted three specific binding sites on catS for C4-S that are different from those found in the crystal structure of the cathepsin K-C4-S complex. Overall, these results describe a novel glycosaminoglycan-mediated mechanism of catS inhibition and suggest that C4-S may modulate the collagenase activity of catS in vivo.