In the present work, four types of graphene/nanotwinned (nt) metal composites are constructed by incorporation of graphene into nt-Au, nt-Ag, nt-Al and nt-Ni matrices, respectively. Their mechanical properties and deformation behaviors are investigated by using molecular dynamics (MD) simulations. Strong strain hardening is found in both Gr/nt-Au and Gr/nt-Ag due to fast structural transition. The transition begins with the propagation of partial dislocations, followed by lattice rotation with the formation of stacking faults, finally resulting in the formation of ultrahigh-density twins with high similarity to the experimental findings. The strain-hardening behavior can only be obtained under uniaxial compression along [1 -1 -2] direction, showing a high orientation dependence. Graphene wrinkles and symmetrical lattice structure in nt-metal matrices are two key factors for a smooth structural transition with strong strain-hardening in Gr/nt-Au and Gr/nt-Ag. However, there is no strain hardening in Gr/nt-Al and Gr/nt-Ni, as the wrinkling of graphene cannot induce the nucleation of dislocations in nt-Al and nt-Ni matrices. This work provides a valuable guideline for the design and application of graphene-reinforced metal matrix composites.