Magnesium-based composites reinforced with stable icosahedral quasicrystal particles have been fabricated via Repeated Plastic Working (RPW) process. The microstructure of the composites has been investigated by XRD, SEM, TEM and HREM, and its mechanical properties have also been studied. The results showed that the RPW process could reduce the matrix grain size significantly, and the average grain size of matrix was only about 500 nm after 200 cycles of RPW. A good metallurgical bond interface between the quasicrystal particles and the Mg matrix was found. The composites exhibited the maximum yield strength of 265MPa and the maximum ultimate tensile strength of 309MPa at room temperature, respectively. The enhancement of mechanical properties is attributed to the strengthening effect of the quasicrystal particles and the fine-grain size of matrix.