A new elevated-temperature high-strength Mg-4Er-2Y-3Zn-0.4Mn (wt %) alloy was developed by semi-continuous casting, solid solution treatment, and hot extrusion. W phase (Mg(Er,Y)Zn) with fcc structure, long period stacking ordered phases with 18R (Mg(Er,Y)Zn) and 14H (Mg(Er,Y)Zn) structures, and basal plane stacking faults (SFs) was formed in the as-cast alloy, mainly due to the alloy component of (Er + Y)/Zn = 1:1 and Er/Y = 1:1 (at %). After solid solution treatment and hot extrusion, the novel microstructure feature formed in as-extruded alloy is the high number-density nanospaced basal plane SFs throughout all the dynamically recrystallized (DRXed) and un-DRXed grains, which has not been previously reported. The as-extruded alloy exhibits superior tensile properties from room temperature to 300 °C. The tensile yield strength can be maintained above 250 MPa at 300 °C. The excellent elevated-temperature strength is mainly ascribed to the formation of nanospaced basal plane SFs throughout the whole Mg matrix, fine DRXed grains ~2 μm in size, and strongly basal-textured un-DRXed grains with profuse substructures. The results provide new opportunities for the development of deformed Mg alloys with satisfactory mechanical properties for high-temperature services.