Micro-alloying design of wrought magnesium (Mg) alloys is an important strategy to achieve high mechanical properties at a low cost. In the last two decades, significant progress has been made from both theory and experiment. In the present review, we try to summarize recent advances in micro-alloying design of wrought Mg alloys from both theoretical and pragmatic perspectives, and provide fundamental data required for establishing the relationship between chemical composition and mechanical properties of Mg alloys. We start with theoretical attempts for understanding the mechanical properties of Mg alloys at different scales, by involving first principle calculations, molecular dynamics, cellular automata, and crystal plasticity. Then, the role of alloying elements is discussed for a series of promising Mg alloys such as Mg-Al, Mg-Zn, Mg-RE (rare-earth element), Mg-Sn, and Mg-Ca families. Potential challenges in the micro-alloying design of Mg alloys are highlighted at the end. The review is expected to provide helpful guidance for the intelligent design of novel wrought Mg alloys and inspire more innovative ideas in this field.