The term ‘nano-crystalline’ refers to a group of metals, abbreviated as NC metals, with typical grain sizes of a few hundred nanometres. An increase in static strength of NC metals allows one to expect an increase in fatigue strength as well. Most of the improved mechanical properties observed in NC metals are attributed to the reduction in grain size; improvements that can be lost if the nano-grains evolves away from the NC state. Fatigue failure due to repetitive loading of metals is a pervasive engineering concern. Unfortunately studies into the fatigue mechanisms are very limited. The aim of this work is to develop a better understanding of fatigue-induced grain growth in NC metals. The nanostructured titanium alloys are due to be used to manufacture high-strength fasteners in the aerospace sector. Thus the research will contribute to their fatigue lifetime prediction.