Graphene shows great potential applications as a solid lubricant in micro- and nanoelectromechanical systems (MEMS/NEMS). An atomic-scale friction strengthening effect in a few initial atomic friction periods usually occurred on few-layer graphene. Here, velocity dependent friction strengthening was observed in atomic-scale frictional behavior of graphene by atomic force microscopy (AFM). The degree of the friction strengthening decreases with the increase of velocity first and then reaches a plateau. This could be attributed to the interaction potential between the tip and graphene at high velocity which is weaker than that at low velocity, because the strong tip-graphene contact interface needs a longer time to evolve. The subatomic-scale stick-slip behavior in the conventional stick-slip motion supports the weak interaction between the tip and graphene at high velocity. These findings can provide a deeper understanding of the atomic-scale friction mechanism of graphene and other two-dimensional materials.