We present a detailed study of a new mathematical object in E-6(6) R+ generalised geometry called an 'exceptional complex structure' (ECS). It is the extension of a conventional complex structure to one that includes all the degrees of freedom of M-theory or type IIB supergravity in six or five dimensions, and as such characterises, in part, the geometry of generic supersymmetric compactifications to five-dimensional Minkowkski space. We define an ECS as an integrable U*(6) x R+ structure and show it is equivalent to a particular form of involutive subbundle of the complexified generalised tangent bundle L-1 subset of E-C We also define a refinement, an SU*(6) structure, and show that its integrability requires in addition a vanishing moment map on the space of structures. We are able to classify all possible ECSs, showing that they are characterised by two numbers denoted `type' and 'class'. We then use the deformation theory of ECS to find the moduli of any SU*(6) structure. We relate these structures to the geometry of generic minimally supersymmetric flux backgrounds of M-theory of the form R-4,R-1 x M, where the SU*(6) moduli correspond to the hypermultiplet moduli in the lower-dimensional theory. Such geometries are of class zero or one. The former are equivalent to a choice of (non-metric-compatible) conventional SL(3, C) structure and strikingly have the same space of hypermultiplet moduli as the fluxless Calabi-Yau case.