Chemokines are important immune proteins, carrying out their function by binding to glycosaminoglycans (GAGs) on the endothelial surface and to cell surface chemokine receptors. A unique viral chemokine analogue, viral macrophage inflammatory protein-II (vMIP-II), encoded by human herpesvirus-8, has garnered interest because of its ability to bind to multiple chemokine receptors, including both HIV coreceptors. In addition, vMIP-II binds to cell surface GAGs much more tightly than most human chemokines, which may be the key to its anti-inflammatory function in vivo. The goal of this work was to determine the mechanism of binding of GAG by vMIP-II. The interaction of vMIP-II with a heparin-derived disaccharide was characterized using NMR. Important binding sites were further analyzed by mutagenesis studies, in which corresponding vMIP-II mutants were tested for GAG binding ability using heparin chromatography and NMR. We found that despite having many more basic residues than some chemokines, vMIP-II shares a characteristic binding site similar to that of its human analogues, utilizing basic residues R18, R46, and R48. Interestingly, a particular mutation (Leu13Phe) caused vMIP-II to form a pH-dependent CC chemokine-type dimer as determined by analytical ultracentrifugation and NMR. To the best of our knowledge, this is the first example of engineering a naturally predominantly monomeric chemokine into a dissociable dimer by a single mutation. This dimeric vMIP-II mutant binds to heparin much more tightly than wild-type vMIP-II and provides a new model for studying the relationship between chemokine quaternary structure and various aspects of function. Structural differences between monomeric and dimeric vMIP-II upon GAG binding were characterized by NMR and molecular docking.