In this study, firstly, in order to achieve fine grains in solid solution strengthened AZ31 magnesium alloy by friction stir processing (FSP), various efforts have been made. It has found that with a newly designed cooling system, the microstructure of commercial AZ31 alloy can be refined dramatically by carefully controlling the FSP parameters. It is of scientific interest that nanometer grains have been observed in the resultant microstructure for the AZ alloy experienced by two-pass FSP. Besides, in order to modify the microstructure and mechanical properties, FSP is also applied to incorporate AZ31 Mg alloy with nano-ZrO2 particles, nano-SiO2 particles and different fractions of Al and Zn elements. The microstructure and mechanical properties of the modified alloy and composite samples are investigated and compared. By one-pass FSP coupled with rapid heat sink from liquid nitrogen cooling approach, the ultrafine grain size in AZ31 Mg alloy is successfully achieved. The grain boundaries are well defined and the mean grain size can be refined to 100~300 nm from the initial 75 £gm of commercial AZ31 Mg alloys sheets. The ultrafine grained structure can drastically increases the microhardness from the initial 50 up to 120 Hv, or an increment factor of 2.4 times. Furthermore, the nanometer grains can be even achieved by two passes FSP coupled with rapid heat sink. The resulting microstructure exhibits equiaxed grains ranging from 40 nm to 200 nm with an average grain size of less than 100 nm. The nanocrystalline grains can be characterized by the TEM observations and the diffraction rings in SAD patterns. The highest hardness point can reach ~150 Hv which is equal to triple of the AZ31 matrix, and the mean hardness also increases up to around 134 Hv. Bulk Mg-AZ31 based composites with 10~20 vol% of nano-ZrO2 particles and 5~10 vol% of nano-SiO2 particles are also successfully fabricated by FSP. The average grain size of the resultant composites could be effectively refined to 2~4 £gm, and it demonstrates much higher hardness values compared to commercial AZ31 billet. Moreover, for the Mg/ZrO2 composite fabricated by one pass and subsequent cooling pass FSP, the recrystallized grain size could be further refined to 0.4 £gm with the hardness value of 135 Hv. As for multi-element Mg base alloys fabricated by FSP, high fractions of Al and Zn elements can result in apparent grain refinement, this can be proved by the broadening of diffraction peaks. Multi-passes FSP can induce the appearance of intermetallic compounds, however, some of them are quasi-crystals with icosahedral point group symmetry. The average hardness of the resultant alloys reachs nearly 350 in Hv scale due to the generation of intermetallic compounds and grain refinement.