In a proteomic search for heparan sulfate-binding proteins on monocytes, we identified HMGB1 (high mobility group protein B1). The extracellular role of HMGB1 as a cytokine has been studied intensively and shown to be important as a danger-associated molecular pattern protein. Here, we report that the activity of HMGB1 depends on heparan sulfate. Binding and competition studies demonstrate that HMGB1 interacts with CHO and endothelial cell heparan sulfate. By site-directed mutagenesis, we identified a loop region that connects the A-box and B-box domains of HMGB1 as responsible for heparan sulfate binding. HMGB1-induced Erk1/2 and p38 phosphorylation is abolished when endothelial heparan sulfate is removed or blocked pharmacologically, resulting in decreased HMGB1-induced endothelial sprouting. However, mutated HMGB1 that lacks the heparan sulfate-binding site retained its signaling activity. We show the major receptor for HMGB1, receptor for advanced glycation end products (RAGE), also binds to heparan sulfate and that RAGE and heparan sulfate forms a complex. Our data establishes that the functional receptor for HMGB1 consists of a complex of RAGE and cell surface heparan sulfate.