A Brillouin scattering investigation has been carried out on trehalose-water solutions in a wide range of concentrations (0 < phi < 0.74) in the ultraviolet regime. A complete set of data as a function of temperature (-10 degrees C <= T <= 100 degrees C) has been obtained for each concentration. The T-phi evolution of the system has been analyzed in terms of energy position and line width of inelastic peaks. These results have been used to derive the structural relaxation time, tau, of the system. This was found to be in the tens of picoseconds time scale, and its T dependence can be described with an activation (Arrhenius) law. Most importantly, a significant slowing down of the relaxation dynamics has been observed as trehalose concentration was increased. At low phi, the activation energy of the relaxation has been found to be consistent with literature data for pure water and comparable with intermolecular hydrogen bond (HB) energy. This evidence strongly supports the hypothesis that the main microscopic mechanism responsible for the relaxation process in trehalose solutions lies in the continuous rearrangement of the HB network. Finally, the results are discussed in terms of the evolution of the system upon increasing trehalose concentration, in order to provide a complete description of the viscoelastic stiffening in real biological conditions.