Solute-solute interactions play a major role in the properties of materials. In this work, we present an extensive database of solute-solute binding energies that captures the detailed interactions in Mg-based alloys from first-principles calculations based on density functional theory. The effects of solute-solute binding energies on magnesium properties, precipitation hardening responses and stacking fault energies in particular, are inferred and discussed. The results of our calculations regarding bindings between solutes with different chemistries, including Al-Sn, Al-Ca, Ca-Zn, Ca-In, and Sn-Zn, were validated using available experimental investigations. Solute pairs that were predicted to show large positive (e.g., Yb-Bi/Sn/Pb and Ca-Bi/Sn/Pb) and negative (e.g., Bi-Sn/Pb/Al) values of binding energies exhibited potential in modifying the precipitation sequence and stacking fault energy. Moreover, alloys added with these alloying elements may exhibit unique mechanical properties, which await experimental verification. Finally, the effect of physical features, including atomic radius and electronegativity, on the solute-solute bindings was investigated. (C) 2015 Elsevier B.V. All rights reserved.