Effects of various friction stir processing (FSP) variables on the microstructural evolution and microhardness of the AZ31 magnesium alloy were investigated. The processing variables include rotational and travelling speed of the tool, kind of second phase (i.e., diamond, Al2O3, and ZrO2) and groove depth (i.e., volume fraction of second phase). Grain size, distribution of second phase particle, grain texture, and microhardness were analyzed as a function of the FSP process variables. The FSPed AZ31 composites fabricated with a high heat input condition showed the better dispersion of particle without macro defect. For all composite specimens, the grain size decreased and the microhardness increased regardless of the grooved depth compared with that of the FSPed AZ31 without strengthening particle, respectively. For the AZ31/diamond composite having a grain size of about 1 μm, microhardness (i.e., about 108 Hv) was about two times higher than that of the matrix alloy (i.e., about 52 Hv). The effect of second phase particle on retardation of grain growth and resulting hardness increase was discussed.