Predictive modeling of strength from first-principles electronic structure methods offers great promise to inform Mg alloy design. Simulating the mechanical behavior for new alloys requires an understanding of mechanisms for deformation at atomic-length scales, with accurate chemistry, extended to larger length- and time-scales. To design ductile Mg alloys, we identify solutes that strengthen basal slip and increase cross-slip. First-principles modeling of dislocations predict dislocation motion under stress through a field of solutes at a finite temperature. First-principles flexible boundary conditions compute accurate core structures of basal and prismatic dislocations, and dislocation/solute interactions. We develop new models to predict the solute-strengthening for basal dislocations; cross-slip from basal- to prismatic-slip for á-type screw dislocations; and cross-slip stress with solutes. First-principles data provides insight into the response of dislocations to solutes and quantitative data to build new predictive models.