Chemokines are small proteins, promoting directional migration and activation of different cells through binding to specific receptors. Most chemokines also bind to heparan sulfate (HS), a family of complex and highly sulfated glycosaminoglycan (GAG) found at the cell surface and in the extracellular matrix. This class of molecules has recently emerged as critical regulators of many events involving cell response to the external environment. Binding to HS is thought to be functionally important. Current models suggested that HS ensures the correct positioning of chemokines within tissues and maintains haptotactic gradients of the proteins along cell surfaces, thus providing directional cues for migrating cells. On the chemokine surface, the GAG binding epitopes can be displayed on different areas, some of which overlap the receptor binding domain, while others are clearly separated. We review here some structural aspects of the interaction between GAGs or receptors and chemokines. In particular, we will address the case of CXCL12, a chemokine whose receptor binding site is distinct from the GAG binding site and whose different isoforms display different GAG binding abilities. This chemokine system thus offers an unprecedented opportunity to ascertain the importance of chemokine/GAG interaction in the regulation of cell migration.