We present a detailed study of a new mathematical object in E6(6)ℝ+ 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) × ℝ+ structure and show it is equivalent to a particular form of involutive subbundle of the complexified generalised tangent bundle L1 ⊂ Eℂ. 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 ℝ4,1 × 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, ℂ) structure and strikingly have the same space of hypermultiplet moduli as the fluxless Calabi-Yau case.