A nano-grain Mg solid solution with a long periodic hexagonal structure was found in Mg97Zn1Y2 and Mg96Zn1Y3 (at%) alloys in a bulk form prepared by warm extrusion of atomized powders at 573 K. The novel structure has an ABACAB-type six layered packing with lattice parameters of a=0.322 nm and c=3x0.521 rim. The Mg solid solution in the former 2%Y alloy has fine grain sizes of 100 to 150 nm and contains 0.78 at%Zn and 1.82 at%Y. In addition, cubic Mg24Y5 particles with a size of about 7 nm are dispersed at small volume fractions of less than 10 % in the Mg matrix. The density (rho) of the extruded rods was 1.840 Mg/m(3) for the 2%Y alloy and 1.860 Mg/m(3) for the 3%Y alloy. The tensile yield strength (sigma(y)) and elongation (delta) at room temperature are 610 MPa and 5 %, respectively, for the 2%Y alloy and 590 MPa and 4 %, respectively, for the 3%Y alloy and the specific yield strength defined by the ratio of sigma(y) to rho is as high as 3.3x10(5) and 3.1x10(5) Nm/kg, respectively. High sigma(y) values exceeding 400 MPa are also maintained at temperatures up to 473 K. The sigma(y) levels are 2.5 to 5 times higher than those for conventional high-strength type Mg-based alloys. The 2%Y alloy also exhibits a high-strain rate superplasticity with large delta of 700 to 800 % at high strain rates of 0.1 to 0.2 s(-1) and 623 K. The excellent mechanical properties are due to the combination of the fine grain size, new long periodic hexagonal solid solution containing Y and Zn, and dispersion of fine Mg24Y5 particles, The new Mg-based alloys are expected to be used in many fields.