Heterostructured metals and alloys are a new class of materials in which mechanical behaviors between the heterogeneous regions are significantly different, and the mechanical properties of bulk materials are superior to the superposition of individual regions. In this paper, three distinct types of heterostructures were constructed in Mg-2.77Y (wt.%) alloy by applying simple thermomechanical processing. Namely, Type I: the non-recrystallized grains of several tens of microns were embedded in the micron-scaled recrystallized grains that were distributed along shear bands and dispersed near grain boundaries; Type II: the aggregations of micron-scaled recrystallized grains were surrounded by the non-recrystallized grains; Type II: the micron-scaled recrystallized grains dominated the microstructure, and the non-recrystallized regions with diameters of tens of micrometers were surrounded by those fine recrystallized grains. Mechanical tests showed that the material with type III heterostructure had the optimal combination of yield strength and uniform elongation. This is attributed to its remarkable hetero-deformation induced (HDI) strengthening and dislocation strengthening. At the initial stage of plastic deformation (engineering strain below 4%), the rapid accumulation of geometrically necessary dislocations (GNDs) at the interfaces between recrystallized and non-recrystallized regions and between neighboring recrystallized grains lead to the significant HDI strengthening. As deformation proceeded, the HDI strengthening effect gradually decreased, and the traditional dislocation strengthening that was caused by GNDs accumulation at grain boundaries became significant. In-situ electron back-scattered diffraction (EBSD) testing revealed that the non-basal slip in the non-recrystallized regions became more remarkable in the late stage of deformation, which improved ductility and strain hardening of the alloy. These findings provide new insight into the design of high-performance hexagonal close-packed structural materials by using the concept of HDI strengthening.