Sliding contact exposes materials to extremely high stresses near the surface, dramatic strain gradients, and frictional heating, all of which can lead to coarsening of nanostructured metals. At the same time, these materials are easily deposited and have high hardnesses, meaning they are natural candidates for wear-resistant coatings. In this talk, we discuss how wear testing conditions, surface microstructure, and wear rate are intimately connected in nanocrystalline metals. First, nanoscratch experiments allow for instantaneous wear rates to be measured and site-specific transmission electron microscopy investigation to occur. We find a variety of microstructures, including gradient nanostructured and laminate configurations, with each type connected to a distinct wear rate. Finally, we attempt to create “structural evolution maps,” analogous to the familiar maps used for creep and wear mechanisms, to clearly show how testing parameters influence the different types of structural evolution observed during the extreme conditions of wear.