The ability of chemokines to bind to glycosaminoglycans (GAGs) on cell surfaces and in the extracellular matrix is thought to play a crucial role in chemokine function. We investigated the structural basis for chemokine binding to GAGs by using in vitro mutagenesis to identify amino acids of chemokine macrophage-inflammatory protein-1 beta (MIP-1 beta) that contribute to its interaction with the model GAG heparin. Among six basic residues that are organized into a single basic domain in the folded MIP-1 beta monomer, three (R18, K45, and R46) were found to contribute significantly to heparin binding. Of these, R46 was found to play a dominant role, and proved essential for the interaction of MIP-1 beta with both heparin and heparan sulfate in physiological salt. The results of this mutational analysis have implications for the structure of the MIP-1 beta-heparin complex, and a comparison of these results with those obtained by mutational analysis of the MIP-1 alpha-heparin interaction suggests a possible structural difference between the MIP-1 beta-heparin and MIP-1 alpha-heparin complexes. To determine whether GAG binding plays an important role in receptor binding and cellular activation by MIP-1 beta, the activities of wild-type MIP-1 beta and R46-substituted MIP-1 beta were compared in assays of T lymphocyte chemotaxis. The two proteins proved equipotent in this assay, arguing that interaction of MIP-1 beta with GAGs is not intrinsically required for functional interaction of MIP-1 beta with its receptor.