The flow stress behavior of an as-spray-deposited AZ31 magnesium alloy with fine grains was investigated by means of compression tests with a Gleeble 1500 thermal mechanical simulator at isothermal constant strain rates of 0.01, 0.1, 1.0, and 10 s−1; the testing temperatures ranged from 623 to 723 K. It is demonstrated that a linear equation can be fitted between the Zemer-Hollomon parameter Z and stress in a double-log scale. The effect of deformation parameters on the behavior of recrystallization was analyzed. Dynamic recrystallization (DRX) generally occurs at a higher temperature and at a lower strain rate. The constitutive equation of the spray-deposited AZ31 magnesium alloy is presented by calculating the deformation activation energy (199.8 kJ·mol−1). The as-spray-formed AZ31 alloy is easier for DRX nucleation at elevated temperatures due to the fine grain, which provides a large amount of nucleation sites and a high-diffusivity path for the atom.