The ability to interact with cell surface glycosaminoglycans (GAGs) is essential to the cell migration properties of chemokines, but association with soluble GAGs induces the oligomerization of most chemokines including CXCL12. Monomeric CXCL12, but not dimeric CXCL12, is cardioprotective in a number of experimental models of cardiac ischemia. We found that co-administration of heparin, a common treatment for myocardial infarction, abrogated the protective effect of CXCL12 in an ex vivo rat heart model for myocardial infarction. The interaction between CXCL12 and heparin oligosaccharides has previously been analyzed through mutagenesis, in vitro binding assays, and molecular modeling. However, complications from heparin-induced CXCL12 oligomerization and studies using very short oligosaccharides have led to inconsistent conclusions as to the residues involved, the orientation of the binding site, and whether it overlaps with the CXCR4 N-terminal site. We used a constitutively dimeric variant to simplify the NMR analysis of CXCL12-binding heparin oligosaccharides of varying length. Biophysical and mutagenic analyses reveal a CXCL12/heparin interaction surface that lies perpendicular to the dimer interface, does not involve the chemokine N terminus, and partially overlaps with the CXCR4-binding site. We further demonstrate that heparin-mediated enzymatic protection results from the promotion of dimerization rather than direct heparin binding to the CXCL12 N terminus. These results clarify the structural basis for GAG recognition by CXCL12 and lend insight into the development of CXCL12-based therapeutics.