We study aqueous solutions of the amphiphilic osmolyte trimethylamine-N-oxide (TMAO) using broadband dielectric spectroscopy and femtosecond mid-infrared spectroscopy. Both experiments provide strong evidence for distinctively slower rotation dynamics for water molecules interacting with the hydrophobic part of the TMAO molecules. Further, water is found to interact more strongly at the hydrophilic site of the TMAO molecules: we find evidence for the formation of stable, TMAO center dot 2H(2)O and/or TMAO center dot 3H(2)O complexes. While this coordination structure seems obvious, the lifetime of these complexes is found to be extraordinarily long (>50 ps). The existence of these long-lived complexes leads to pronounced parallel dipole correlations between water and TMAO, reflected in enhanced amplitudes in the dielectric spectra. The strong interaction between water and TMAO also results in a red-shifted band for the O-D stretching vibration of HDO molecules in an isotopically diluted aqueous TMAO solution. This O-D stretching vibration has a vibrational lifetime of 670 fs, which is significantly shorter than the lifetime of the O-D stretch vibration of bulk-like HDO molecules, presumably due to efficient coupling to vibrational modes of TMAO. The rotational dynamics of these O-D groups are slowed down dramatically, and are limited by the rotation of the whole complex, while the O-D vector oriented away from TMAO probably shows an accelerated reorientation.