Chemokines and galectins are simultaneously upregulated and mediate leukocyte recruitment during inflammation. Until now, these effector molecules have been considered to function independently. Here, we tested the hypothesis that they form molecular hybrids. By systematically screening chemokines for their ability to bind galectin‐1 and galectin‐3, we identified several interacting pairs, such as CXCL12 and galectin‐3. Based on NMR and MD studies of the CXCL12/galectin‐3 heterodimer, we identified contact sites between CXCL12 β‐strand 1 and Gal‐3 F‐face residues. Mutagenesis of galectin‐3 residues involved in heterodimer formation resulted in reduced binding to CXCL12, enabling testing of functional activity comparatively. Galectin‐3, but not its mutants, inhibited CXCL12‐induced chemotaxis of leukocytes and their recruitment into the mouse peritoneum. Moreover, galectin‐3 attenuated CXCL12‐stimulated signaling via its receptor CXCR4 in a ternary complex with the chemokine and receptor, consistent with our structural model. This first report of heterodimerization between chemokines and galectins reveals a new type of interaction between inflammatory mediators that can underlie a novel immunoregulatory mechanism in inflammation. Thus, further exploration of the chemokine/galectin interactome is warranted. Synopsis Chemokines and galectins are simultaneously upregulated during inflammation and mediate leukocyte recruitment. A systematic screen now demonstrates their physical interaction as heterodimers, identifying several novel interacting pairs. Chemokines and galectins can engage in cross talk by pairing, as exemplified by galectin‐3 and CXCL12. The association of CXCL12 with galectin‐3 appears to have potential for modulating chemokine activity. Galectin‐3 inhibits CXCL12‐induced chemotaxis of leukocytes and their recruitment to inflammation sites. Galectin‐3 attenuates CXCL12‐stimulated signaling via its receptor CXCR4 in a ternary complex. Chemokines and galectins are simultaneously upregulated during inflammation and mediate leukocyte recruitment. A systematic screen now demonstrates their physical interaction as heterodimers, identifying several novel interacting pairs.