Deficiency of glycosaminoglycan (GAG) degradation causes a subclass of lysosomal storage disorders called mucopolysaccharidoses (MPSs), many of which present with severe neuropathology. Critical steps in the degradation of the GAG heparan sulfate remain enigmatic. Here we show that the lysosomal arylsulfatase G (ARSG) is the long-sought glucosamine-3-O-sulfatase required to complete the degradation of heparan sulfate. Arsg-deficient mice accumulate heparan sulfate in visceral organs and the central nervous system and develop neuronal cell death and behavioral deficits. This accumulated heparan sulfate exhibits unique nonreducing end structures with terminal N-sulfoglucosamine-3-O-sulfate residues, allowing diagnosis of the disorder. Recombinant human ARSG is able to cleave 3-O-sulfate groups from these residues as well as from an authentic 3-O-sulfated N-sulfoglucosamine standard. Our results demonstrate the key role of ARSG in heparan sulfate degradation and strongly suggest that ARSG deficiency represents a unique, as yet unknown form of MPS, which we term MPS IIIE.