Severe corrosion of Mg and Mg alloys is a major issue hindering their wider application in transportation industry, medical implants and aqueous batteries. Previously, no Mg-based material has been found with a significantly lower corrosion rate than that of ultra-high-purity Mg, i.e. 0.25 mm y-1 in concentrated NaCl solution. In this work for the first time, highly corrosion-resistant Mg is found to be accomplishable by Ca micro-alloying, bringing "stainless Mg" closer. The designed Mg-Ca lean alloys possess incredibly low corrosion rates, less than 0.1 mm y-1 in 3.5 wt% NaCl solution, which are significantly lower than that of ultra-high-purity Mg and all Mg alloys reported thus far. The outstanding corrosion resistance is attributed to inhibition of cathodic water reduction kinetics, impurities stabilizing and a protective surface film induced by Ca micro-alloying. Combined with the environmental benignity and economic viability, Ca micro-alloying renders huge feasibility on developing advanced Mg-based materials for diverse applications.