In this work, graphene nanoplatelets (GNPs) reinforced magnesium (Mg) matrix composites were synthesised using the multi-step dispersion route. Well-dispersed but inhomogeneously distributed GNPs were obtained in the matrix. Compared with the monolithic alloy, the nanocomposites exhibited dramatically enhanced Young’s modulus, yield strength and ultimate tensile strength and relatively high plasticity, which mainly attributed to the significant heterogeneous laminated microstructure induced by the addition of GNPs. With increasing of the concentration of GNPs, mechanical properties of the composites were gradually improved. Especially, the strengthening efficiency of all the composites exceeded 100%, which was significantly higher than that of carbon nanotubes reinforced Mg matrix composites. The grain refinement and load transfer provided by the two-dimensional and wrinkled surface structure of GNPs were the dominated strengthening mechanisms of the composites. This investigation develops a new method for incorporating GNPs in metals for fabricating high-performance composites.