Recently, there have been few reports on the hot extrusion process of magnesium (Mg) alloy square tubes. In this work, we introduce a novel hot extrusion process called tube continuous expanding shear extrusion (tCESE) to produce Mg alloy square tubes with heterogeneous structures. Compared to previously reported hot-extruded Mg alloy tubes, the tCESE samples exhibit simultaneous enhancements in both strength and ductility. The microstructure evolution during the tCESE process was analyzed in detail. It was found that the microstructure developed consecutively as a result of twinning-induced dynamic recrystallization (TDRX), discontinuous dynamic recrystallization (DDRX) and continuous dynamic recrystallization (CDRX) with different nucleation of new orientations, while static recrystallization (SRX) promoted the formation of heterogeneous structures. The strengthening mechanism in the tCESE samples was revealed by loading-unloading-reloading (LUR) tensile tests, viscoplastic self-consistent (VPSC) simulation and intermittent tensile tests. The improvement of the strength in the tCESE samples is attributed to the size refinement of the grains and the second-phases, and more importantly, to hetero-deformation induced (HDI) strengthening. The improvement of the ductility in the tCESE samples can be attributed to the significant increase in non-basal dislocations within the heterogeneous structures during tensile deformation.