In this work, a novel process of repeated upsetting-extrusion (RUE) was used to fabricate the AQ80 magnesium (Mg) alloy. The effects of deformation passes on the microstructure and microhardness of the RUEed AQ80 Mg alloy were studied. The results showed that {10–12} extension twins appeared in the sample after 1 pass of deformation compared to the initial sample, which divided the coarse grains and achieved the preliminary refinement of the grains. The grains were uniformly refined further with increasing RUE deformation passes, and after 3 passes, the average grain size was reduced from 27.4 to 3.0 μm. The grains were refined mainly by continuous dynamic recrystallization (CDRX), particle-stimulated nucleation (PSN), and discontinuous dynamic recrystallization (DDRX) mechanisms. After RUE deformation, the peak component of the texture was tilted by 0–20° toward the extrusion direction (ED) because of the increased activation of pyramidal < c + a > slip. The microhardness of the 3-pass RUE deformed sample increased by 12.9% compared to the initial sample. This is mainly attributable to fine-grained strengthening and second phase strengthening.