Femtosecond two-dimensional infrared (2DIR) spectroscopy was carried out to study the dynamics of vibrational spectral diffusion of the nitrile stretching vibration of thiocyanate anions (S-C≡N(-)) dissolved in liquid-to-supercritical heavy water (D2O). The 2DIR line shapes were used to extract through a nodal slope analysis quantitative information about the correlation function for temporal fluctuations of the CN-stretching frequency. The inverse nodal slope could be fitted phenomenologically by a simple double-exponential decay whose predominant component had a time constant ranging between 300 fs and 1 ps depending on the temperature. The temperature dependence is interpreted in terms of solvent structural fluctuations that are driven by the librational motions of the D2O molecules located in the first solvation shell of the anion. Complementary molecular dynamics simulations of the SCN(-)/D2O system indicate that the breaking and making of hydrogen-bonds between the terminal N-atom of the anion and the D2O molecules are induced by the same solvent-shell librational degrees of freedom that drive the vibrational line broadening dynamics seen in the 2DIR experiment.