Crystalline Mg-based alloys with a distinct reduction in hydrogen evolution were prepared through both electrochemical and microstructural engineering of the constituent phases. The addition of Zn to Mg-Ca alloy modified the corrosion potentials of two constituent phases (Mg + Mg2Ca), which prevented the formation of a galvanic circuit and achieved a comparable corrosion rate to high purity Mg. Furthermore, effective grain refinement induced by the extrusion allowed the achievement of much lower corrosion rate than high purity Mg. Animal studies confirmed the large reduction in hydrogen evolution and revealed good tissue compatibility with increased bone deposition around the newly developed Mg alloy implants. Thus, high strength Mg-Ca-Zn alloys with medically acceptable corrosion rate were developed and showed great potential for use in a new generation of biodegradable implants.