Abstract Nuclear magnetic resonance relaxometry represents a powerful tool for extracting dynamic information. Yet, obtaining links to molecular motion is challenging for many ions that relax through the quadrupolar mechanism, which is mediated by electric field gradient fluctuations and lacks a detailed microscopic description. For sodium ions in aqueous electrolytes, we combine ab initio calculations to account for electron cloud effects with classical molecular dynamics to sample long-time fluctuations, and obtain relaxation rates in good agreement with experiments over broad concentration and temperature ranges. We demonstrate that quadrupolar nuclear relaxation is sensitive to subpicosecond dynamics not captured by previous models based on water reorientation or cluster rotation. While ions affect the overall water retardation, experimental trends are mainly explained by dynamics in the first two solvation shells of sodium, which contain mostly water. This work thus paves the way to the quantitative understanding of quadrupolar relaxation in electrolyte and bioelectrolyte systems.