Little is presently known about the unique nanostructure of deep eutectic solvents (DES). The order of the liquid-solid phase transition is contended and whether DES-water mixtures are merely aqueous solutions, or have properties dominated by the eutectic pair, is unclear. Here, we unambiguously show the structure of choline chloride-malic acid (malicine) as a liquid, and also in solid and hydrated forms, using neutron total scattering on D/H isotope-substituted samples, and quasi-elastic neutron scattering (QENS). Data were refined using empirical potential structure refinement. We show evidence for a stoichiometric complex ion cluster in the disordered liquid, with strong choline-chloride bonding and a hydrogen bond donor (HBD) contribution. The 1:1 eutectic stoichiometry makes these ionic domains more well-defined, with less HBD clustering than seen previously for reline. There is minimal structural difference for the solidified material, demonstrating that this DES solidification is a glass transition rather than a first order phase change. QENS data support this by showing a gradual change in solvent dynamics rather than a step change. The DES structure is mostly retained upon hydration, with water acting both as a secondary smaller HBD at closer range to choline than malic acid, and forming transient wormlike aggregates. This new understanding of DES structure will aid understanding of the properties of these novel green solvents on the molecular length scale in chemical processes, as well as giving an insight into the apparent role of natural DESs in plant physiology.