  We present a detailed study of a new mathematical object in
$\mathrm{E}_{6(6)}\times \mathbb{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
$\mathrm{U}^{*}(6)\times \mathbb{R}^{+}$ structure and show it is equivalent to
a particular form of involutive subbundle of the complexified generalised
tangent bundle $L_{1} \subset E_{\mathbb{C}}$. We also define a refinement, an
$\mathrm{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 $\mathrm{SU}^{*}(6)$ structure. We relate these structures to
the geometry of generic minimally supersymmetric flux backgrounds of M-theory
of the form $\mathbb{R}^{4,1}\times M$, where the $\mathrm{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 $\mathrm{SL}(3,\mathbb{C})$ structure and
strikingly have the same space of hypermultiplet moduli as the fluxless
Calabi--Yau case.
