Heparan sulfate (HS) proteoglycans bind extracellular proteins that participate in cell signaling, attachment and endocytosis. These interactions depend on the arrangement of sulfated sugars in the HS chains generated by well-characterized biosynthetic enzymes; however, the regulation of these enzymes is largely unknown. We conducted genome-wide CRISPR–Cas9 screens with a small-molecule ligand that binds to HS. Screening of A375 melanoma cells uncovered additional genes and pathways impacting HS formation. The top hit was the epigenetic factor KDM2B, a histone demethylase. KDM2B inactivation suppressed multiple HS sulfotransferases and upregulated the sulfatase SULF1. These changes differentially affected the interaction of HS-binding proteins. KDM2B-deficient cells displayed decreased growth rates, which was rescued by SULF1 inactivation. In addition, KDM2B deficiency altered the expression of many extracellular matrix genes. Thus, KDM2B controls proliferation of A375 cells through the regulation of HS structure and serves as a master regulator of the extracellular matrix. [Figure not available: see fulltext.]