Zn-Mn alloys are particularly promising biodegradable implant materials, but they are plagued by poor mechanical performance. In this work, a Zn-Mn alloy with ultrahigh strength and excellent ductility was achieved through addition of trace Mg (0.1 wt%) and equal channel angular pressing (ECAP). Specifically, the ECAP processed Zn-0.5Mn-0.1 Mg alloy exhibits an ultimate tensile strength (UTS) of 428 MPa, which is highest ever achieved in Zn-Mn-based alloys, along with a good elongation (EL) of 39%. In addition, the alloy exhibits excellent antibacterial performance against Staphylococcus aureus (S. aureus) and Escherichia coli (E. coli). Trace Mg addition results in the formation of Mg2Zn11 and MgZn2 nano-precipitates in the alloy, which effectively pins grain growth during dynamic recrystallization (DRX) and postpones the inverse Hall–Petch relation. Consequently, the alloy possesses quite fine grains of an average grain size (AGS) of 0.71 μm, much smaller than that of its counterpart without Mg (AGS = 2.54 μm). The ultrahigh strength of the alloy is mainly ascribed to grain boundary strengthening and precipitation strengthening. The remarkable ductility of the alloy is related to deformation twinning suppression, pyramidal < c + a > slip activation, and low dislocation density.