Pure magnesium exhibits poor ductility owing to pyramidal < c + a > dislocation transformations to immobile structures, making this lowest-density structural metal unusable for many applications where it could enhance energy efficiency. We show why magnesium can be made ductile by specific dilute solute additions, which increase the < c + a > cross-slip and multiplication rates to levels much faster than the deleterious < c + a > transformation, enabling both favorable texture during processing and continued plastic straining during deformation. A quantitative theory establishes the conditions for ductility as a function of alloy composition in very good agreement with experiments on many existing magnesium alloys, and the solute-enhanced cross-slip mechanism is confirmed by transmission electron microscopy observations in magnesium-yttrium. The mechanistic theory can quickly screen for alloy compositions favoring conditions for high ductility and may help in the development of high-formability magnesium alloys.