Single-asperity adhesion between nanoscale silicon tips and few-layer graphene (FLG) sheets, as well as graphite, was measured using atomic force microscopy (AFM). The adhesion mechanism was understood through experiments and finite element method (FEM) simulations by comparing conventional pull-forces measurements (contact and separation, without sliding) to those obtained after the tip was slid along the surface before separation (“pre-sliding”). Without pre-sliding, no variation in the pull-off force was measured between consecutive measurements, and there was no observable dependence of the mean pull-off force value on the number of FLG layers. However, when the tip was pre-slid over a local area, the first pull-off force was enhanced by 12–17%; subsequent pull-off forces then relaxed to a lower, constant value. This occurred regardless of the number of layers, and occurred for aged graphite samples as well. Our analysis indicates that this is due to sliding-induced changes of graphene's interfacial geometry, whereby local delamination of the top graphene layer occurs, provided there is sufficient atmospheric exposure of the surface after cleaving. This effect provides another unique feature of the nanotribological behavior of atomically-thin sheets and is consequential for designing graphene-based devices and coatings where adhesive interactions are important.