Owing to its excellent mechanical and tribological properties, graphene has been proposed to be a promising atomically-thin solid lubricant for engineering applications. However, as a typical two-dimensional (2D) material, graphene has an exceptionally high surface-to-volume ratio and is very susceptible to the surrounding environments. By performing nanoscale scratch tests on graphene deposited on four different substrates, we have shown that the anti-wear performance of graphene, characterized by the maximum load carrying capacity, is not an intrinsic material property. Instead, its value is significantly affected by the stiffness the substrates: Stiffer substrate typically results in a higher load carrying capacity. As revealed by finite element simulations, stiffer substrate can effectively share the normal load and reduce the in-plane stress of graphene by limiting graphene deformation, which enhances the overall load carrying capacity. In addition to the load sharing mechanism, the experimental results also suggest that the frictional shear stress during scratch tests may facilitate wear of graphene by lowering its equivalent strength. The deformation mechanism of graphene/substrate systems revealed in this work provides guidelines for optimizing the mechanical performance of 2D materials for a wide range of tribological applications.