Nanocrystalline metals with average grain sizes of only a few nanometers have recently been observed to fail through the formation of shear bands. Here, we investigate this phenomenon in nanocrystalline Ni which has had its grain structure stabilized by doping with W, with a specific focus on understanding how strain localization drives evolution of the nanoscale grain structure. Shear banding was initiated with both microcompression and nanoindentation experiments, followed by site-specific transmission electron microscopy to characterize the microstructure. Grain growth and texture formation were observed inside the shear bands, which had a wide variety of thicknesses. These evolved regions have well-defined edges, which rules out local temperature rise as a possible formation mechanism. No structural evolution was found in areas away from the shear bands, even in locations where significant plastic deformation had occurred, showing that plastic strain alone is not enough to cause evolution. Rather, intense strain localization is needed to induce mechanically-driven grain growth in a thermally-stable nanocrystalline alloy.