This work shows that a soft, thin film comprising randomly aligned carbon nanotubes (CNTs) can reduce surface wear more effectively than a homogeneous thin film because of enhanced elastic recoverability and contact stress relief originating from its mesh structure. To investigate the wear characteristics of the mesh structure compared to those of the homogeneous thin film, multi-walled CNTs (MWCNTs) and diamond-like carbon (DLC) thin films were prepared to conduct nanoscale tribological experiments using the atomic force microscopy (AFM). The MWCNT thin film showed unmeasurably low wear compared with the DLC thin film under a certain range of normal load. To demonstrate the wear reduction mechanism of the MWCNT thin film, its indentation and frictional behaviors were assessed. The indentation behavior of the MWCNT thin film revealed repetitive elastic deformation with a wide strain range and a significantly lower elastic modulus than that of the DLC thin film. The permanent deformation of the MWCNT thin film was observed through frictional experiments under relatively high normal load conditions. These results are expected to provide insights into the design of highly wear-resistant surfaces using nanostructures.