Hedgehog (Hh) morphogens play fundamental roles during embryogenesis and adulthood, in health and disease. Multiple cell surface receptors regulate the Hh signaling pathway. Among these, the glycosaminoglycan (GAG) chains of proteoglycans shape Hh gradients and signal transduction. We have determined crystal structures of Sonic Hh complexes with two GAGs, heparin and chondroitin sulfate. The interaction determinants, confirmed by site-directed mutagenesis and binding studies, reveal a previously not identified Hh site for GAG binding, common to all Hh proteins. The majority of Hh residues forming this GAG-binding site have been previously implicated in developmental diseases. Crystal packing analysis, combined with analytical ultracentrifugation of Sonic Hh-GAG complexes, suggests a potential mechanism for GAG-dependent Hh multimerization. Taken together, these results provide a direct mechanistic explanation of the observed correlation between disease and impaired Hh gradient formation. Moreover, GAG binding partially overlaps with the site of Hh interactions with an array of protein partners including Patched, hedgehog interacting protein, and the interference hedgehog protein family, suggesting a unique mechanism of Hh signaling modulation.