The erosion mechanisms during abrasive waterjet (AWJ) machining have been examined for a variety of materials. However, no systematic study has considered the effect of the microstructure property relationship on the erosion mechanisms in metals. In this work, the influence of microstructure and mechanical properties on the erosion mechanisms is investigated using AWJ controlled-depth milling and single particle impact experiments performed on nanocrystalline, microcrystalline and single crystal nickel samples. The resulting footprints and subsurface microstructure evolution were analysed using advanced characterization techniques. The erosion rate of the target metal is found to correlate positively with grain size and negatively with hardness but this correlation is nonlinear. The subsurface microstructure of the single crystal and microcrystalline are altered, while only the texture of the nanocrystalline nickel is modified. The grain refinement mechanism observed in microcrystalline and single crystal microstructure is elucidated by electron backscatter diffraction. It proceeds by the generation of dislocations under severe plastic deformation, which transforms into subgrains before forming new grains under further strain. Therefore, severe plastic deformation induced by AWJ machining leads to surface nanocrystallization and induces substantial subsurface work-hardening, as revealed by nanoindentation tests and confirmed by single particle impacts, with the consequence that the erosion rate decreases with decreasing grain size. This work clarifies the erosion mechanisms in pure metals and highlights the dynamic nature of AWJ machining as a result of the complex interplay between microstructure, mechanical properties and material removal mechanisms, providing new insights into AWJ controlled-depth milling technique.