The extraordinary mechanical properties of nanocrystalline metals are well documented, though this class of materials often remains impractical for engineering design due to instability in the grain size with the addition of even modest amounts of stress or heat. This change can dramatically reduce the strength of nanocrystalline metals, and adversely impact tribological behavior. While it has been possible to achieve low friction and ultra-low wear with metals, the ability to quantify and predict stability bounds has remained elusive, leaving engineers with only phenomenological models as design tools. We show new and compelling fundamental correlations between experimental and molecular dynamics simulation data, and present a physics-based predictive framework for describing the tribological stability thresholds of nanocrystalline metal contacts. In this context, we address a long-standing causal misconception that higher hardness leads to higher wear resistance, explain the origin and regimes of validity of this notion, and provide a more reliable and quantitative mechanistic model. We conclude with a look at tantalizing prospects for these ideas in the design of next-generation wind turbines, aerospace systems, and nanostructured materials.