Solid-solution strengthening results from solutes impeding the glide of dislocations. Existing theories of strength rely on solute-dislocation interactions, but do not consider dislocation core structures, which need an accurate treatment of chemical bonding. Here, we focus on strengthening of Mg, the lightest of all structural metals and a promising replacement for heavier steel and aluminum alloys. Elasticity theory, which is commonly used to predict the requisite solute-dislocation interaction energetics, is replaced with quantum-mechanical first-principles calculations to construct a predictive mesoscale model for solute strengthening of Mg. Results for 29 different solutes are displayed in a strengthening design map as a function of solute misfits that quantify volumetric strain and slip effects. Our strengthening model is validated with available experimental data for several solutes, including Al and Zn, the two most common solutes in Mg. These new results highlight the ability of quantum-mechanical first-principles calculations to predict complex material properties such as strength.