Proteoglycans (PGs) play a dominant role within the bone marrow (BM), but their role in homing of transplanted hematopoietic progenitor cells (HPC) is unknown. In this study, the role of heparan sulfate (HS) PGs on BM endothelium as adhesive structures was investigated. HPC (primary CD34+ cells and cell line KG-1a) were able to bind fractionated heparin, which could be competed by highly sulfated heparin/HS-glycosaminoglycans (GAGs). Under flow conditions, HPC adhered to immobilized heparin after rolling over E-selectin. Rolling of KG-1a on BM endothelial cell (EC) line 4LHBMEC was completely E selectin-dependent. Addition of heparin/HS-GAGs, endothelial treatment with chlorate, or anti-HS all partially inhibited firm adhesion. Moreover, enzymatic removal of endothelial HS-GAGs reduced initial adhesion. Finally, HPC-bound PGs isolated from 4LHBMEC, which was largely inhibited by enzymatic HS-degradation. In summary, we identified sulfated structures on BM endothelium, most likely HSPGs, as a novel class of glycoconjugates involved in the multistep homing cascade of HPC.