Nanocrystalline metals are distinct from traditional engineering materials due to their high concentration of grain boundaries and corresponding structural disorder at grain boundaries. The effect of local disorder in nanocrystalline materials manifests in ways reminiscent of fully amorphous materials, such as mesoscale shear localization and pressure-dependent yielding, owing to the high concentration of grain boundaries and their predominance in governing plasticity. Relaxation processes in nanocrystalline materials that facilitate reconfigurations of grain boundaries and lower their energy, such as low temperature annealing, have been shown to enhance mechanical strength. However, processes that raise the energy of a nanocrystalline metal have not been observed, limiting the tunability of properties and the prospect for suppressing shear localization. Here, we use femtosecond laser processing as a unique non-equilibrium process that can generate complex stress states due to ultrafast electronic excitation and subsequent relaxation events. Experiments on nanocrystalline Al-O and Cu-Zr alloys indicate that sub-ablation femtosecond laser pulses cause up to an 87% reduction in hardness with no change in grain size, which can be ascribed to grain boundary-mediated processes. Parallels between our results and rejuvenation processes in glassy systems will be discussed in the context of controlling metastable structural configurations through novel processing routes.