AZ31B magnesium alloy prepared by conventional friction stir processing (FSP) usually exhibits an intense basal texture, resulting in an unsatisfactory strength and ductility. In this work, cooling medium-assisted FSP was conducted on the AZ31B magnesium alloy. The effects of a liquid CO₂ coolant on the thermal cycle, microstructure, and mechanical properties of the stir zone (SZ) were evaluated. The adoption of a liquid CO₂ coolant resulted in markedly decreased peak temperature and increased cooling rate. The SZ exhibited a fine grain structure with abundant dislocations and twins. The grain refinement mechanism was attributed to the combinational effect of discontinuous dynamic recrystallization, continuous dynamic recrystallization, and twinning-induced geometric dynamic recrystallization. The SZ showed a best combination of ultimate tensile strength of 293 MPa and fracture elongation of 18.6%. The interaction of dislocations and twins rendered the plastic deformation more stable during tensile testing.