In wrought magnesium alloys, room temperature plasticity is largely controlled by limited slip systems such as basal slip and tension/compression twins. The insufficient number of active slip systems limits strength and ductility preventing broader structural applicability of Mg-alloys. Hence, we employ first-principle calculations to investigate the effects of different alloying elements (Y, Li, Al, Zn, Zr, Sn and Ce) on low temperature strength and formability of Mg-alloys through ideal shear strength. Li, Al, Sn, Zn and Zr show a strengthening effect, whereas Y and Ce lower dislocation nucleation energetics on all the slip systems. Further, comparing our ideal shear strength calculations with available general stacking fault energy calculations provides an overall understanding of dislocation nucleation and motion and we found that Y and Ce addition improves the formability of Mg-alloys. The profound effects of solute addition result from the charge transfer between the solute atom and surrounding magnesium atoms.