Aiming to develop low-cost Mg alloys with good mechanical properties, a new Mg-6Bi-3Al-1Zn (wt.%, BAZ631) alloy having a high ultimate tensile strength of ~402 MPa and an elongation of ~15% was fabricated by single pass extrusion. The as-extruded BAZ631 alloy demonstrates an almost fully dynamic recrystallized microstructure with an average grain size of ~2.9 μm. Moreover, both nano-scale Mg3Bi2 and Mg17Al12 precipitates were found dispersed in the matrix. These excellent mechanical properties are attributed to the combined effects of grain boundary strengthening, dispersion and precipitation strengthening induced by both micro and nanoscale second phase particles, and solid-solution strengthening. This high strength and good ductile Mg-Bi based alloy without rare-earth elements addition is expected to inspire a new alloy design strategy for fabricating high performance Mg products for larger-scale industrial applications.