Grain refinement induced increase in hardness is of interest from a tribological point of view. Most of nanostructured metals show an enhanced wear resistance in comparison with their coarse-grained counterparts. To understand the related wear mechanism, the tribological properties and worn subsurface structure of nanostructured Cu were investigated under both dry and oil-lubricated sliding conditions, respectively. The wear resistance and worn subsurface structure of nanostructured Cu were compared under different conditions. The results indicate that nanostructured Cu exhibits a dynamic recrystallization (DRX) dominated wear mechanism under both conditions. A pronounced correlation is identified that wear rate increases significantly with an increasing grain size or decreasing hardness of DRX structure.