AZ91 magnesium alloy was subjected to a deep cryogenic treatment. X-ray diffraction (XRD), scanning electronic microscopy (SEM), and transmission electronic microscopy (TEM) methods were utilized to characterize the composition and microstructure of the treated samples. The results show that after two cryogenic treatments, the quantity of the precipitate hardening β phase increases, and the sizes of the precipitates are refined from 8–10 μm to 2–4 μm. This is expected to be due to the decreased solubility of aluminum in the matrix at low temperature and the significant plastic deformation owing to internal differences in thermal contraction between phases and grains. The polycrystalline matrix is also noticeably refined, with the sizes of the subsequent nanocrystalline grains in the range of 50–100 nm. High density dislocations are observed to pile up at the grain boundaries, inducing the dynamic recrystallization of the microstructure, leading to the generation of a nanocrystalline grain structure. After two deep cryogenic treatments, the tensile strength and elongation are found to be substantially increased, rising from 243 MPa and 4.4% of as-cast state to 299 MPa and 5.1%.