Heterogeneity and molecular motions in representative cryoprotectant mixtures made of trehalose and glycerol are investigated in the temperature range 298 <= T (K) <= 353, via time resolved fluorescence Stokes shift and anisotropy measurements, and molecular dynamics simulations of four-point density-time correlations and H-bond relaxations. Mixtures containing 5 and 20 wt % of trehalose along with neat glycerol are studied. Viscosity coefficients for these systems lie in the range 0.30 < eta (P) < 23. Measured solute (Coumarin 153) rotation and solvation times reveal a substantial departure from the hydrodynamic viscosity dependence, suggesting the strong microheterogeneous nature of these systems. Fluorescence anisotropy decays are highly nonexponential, reflecting a non-Markovian character of the medium friction. A complete missing of the Stokes shift dynamics in these systems at 298 K but partial detection of it at other higher temperatures (shift magnitude being similar to 400-600 cm(-1)) indicates rigid solute environments. An amorphous solid-like feature emerges in the simulated radial distribution functions at these temperatures. Analyses of mean squared displacements reveal rattling-in-a-cage motion, non-Gaussian displacement distributions, and strong dynamic heterogeneity features. Simulated dynamic structure factors and four-point correlations hint, respectively, at very long a relaxation and correlated time scales at 298 K This explains the long solute rotation times (similar to 80-200 ns) measured at 298 K. Stretched exponential decay of the simulated H-bond relaxations with long time scales further highlights the strong temporal heterogeneity and slow dynamics inherent to these systems. In summary, this work provides the first insight into the molecular motions and interspecies interaction in a representative cryoprotectant mixture, and stimulates further study to investigate the interconnection between cryoprotection and dynamic heterogeneity.