A two-dimensional cellular automaton (CA) model was utilized to analyze the effect of mechanical vibration on microstructure evolution of AZ91 alloy during friction stir welding (FSW). The simulated results, namely grain topology, grain size distribution, average grain size, and also the dynamic recrystallization (DRX) fraction were compared with measured data. The adequate comparability between FEM and experimental data shows that the CA method can be applied to the analysis of the microstructure progression during the friction stir welding of AZ91 alloy. It is concluded that the dislocation density during the friction stir vibration welding (FSVW) is higher than that in the FSW process and the process of nucleation and grain growth is faster for samples during FSVW compared to FSW. The grain size modification and DRX phenomenon with various vibration frequencies were also simulated in detail during FSVW. It is found that vibration makes nucleation start earlier and decreases the proportion of the incubation period and the percentage of recrystallization as vibration frequency improves.