CXCL12 (SDF-1a) and CXCR4 are critical for embryonic development and cellular migration in adults. These proteins are involved in HIV-1 infection, cancer metastasis and WHIM disease. Sequestration and presentation of CXCL12 to CXCR4 by glycosaminoglycans (GAGs) is proposed to be important for receptor activation. Mutagenesis has identified CXCL12 residues that bind to heparin. However, the molecular details of this interaction have not yet been determined. Here we demonstrate that soluble heparin and heparan sulfate negatively affect CXCL12 mediated in vitro chemotaxis. We also show that a cluster of basic residues in the dimer interface is required for chemotaxis and is a target for inhibition by heparin. We present structural evidence for binding of an unsaturated heparin disaccharide to CXCL12 attained through solution NMR spectroscopy and X-ray crystallography. Increasing concentrations of the disaccharide altered 2D-1H-15N-HSQC spectra of CXCL12, which identified two clusters of residues. One cluster corresponds to ß-strands in the dimer interface. The second includes the amino-terminal loop and the a-helix. In the X-ray structure two unsaturated disaccharides are present. One is in the dimer interface with direct contacts between residues His25, Lys27 and Arg41 of CXCL12 and the heparin disaccharide. The second disaccharide contacts Ala20, Arg21, Asn30 and Lys64. This is the first X-ray structure of a CXC class chemokine in complex with glycosaminoglycans. Based on the observation of two heparin binding sites, we propose a mechanism in which GAGs bind around CXCL12 dimers as they sequester and present CXCL12 to CXCR4.