Chemokines are small proteins that are critical for immune function, being primarily responsible for the activation and chemotaxis of leukocytes. As such, many viruses, as well as parasitic arthropods, have evolved systems to counteract chemokine function in order to maintain virulence, such as binding chemokines, mimicking chemokines, or producing analogs of transmembrane chemokine receptors that strongly bind their targets. The focus of this review is the large group of chemokine binding proteins (CBP) with an emphasis on those produced by mammalian viruses. Because many chemokines mediate inflammation, these CBP could possibly be used pharmaceutically as anti-inflammatory agents. In this review, we summarize the structural properties of a diverse set of CBP and describe in detail the chemokine binding properties of the poxvirus-encoded CBP called vCCI (viral CC Chemokine Inhibitor). Finally, we describe the current and emerging capabilities of combining computational simulation, structural analysis, and biochemical/biophysical experimentation to understand, and possibly re-engineer, protein-protein interactions.