Background: Polymyxins have re-entered use against problem Gram-negative bacteria. Resistance rates are uncertain, with estimates confounded by selective testing. Methods: The BSAC Resistance Surveillance Programme has routinely tested colistin since 2010; we reviewed data up to 2017 for relevant Enterobacterales (n = 10914). Unexpectedly frequent resistance was seen among the Enterobacter cloacae complex isolates (n = 1749); for these, we investigated relationships to species, genome, carbon source utilization and LPS structure. Results: Annual colistin resistance rates among E. cloacae complex isolates were 4.4% 20%, with a rising trend among bloodstream organisms; in contrast, annual rates for Escherichia coli and Klebsiella spp. (including K. aerogenes) generally remained 2%. WGS split the E. cloacae complex isolates into seven genogroup clusters, designated A G. Among isolates assigned to genogroups A D, 47/50 sequenced were colistin resistant, and many of those belonging to genogroups A C identified as E. asburiae. Isolates belonging to genogroups E G consistently identified as E. cloacae and were rarely (only 3/45 representatives sequenced) colistin resistant. Genogroups F and G, the predominant colistin-susceptible clusters, were metabolically distinct from other clusters, notably regarding utilization or not of L-fucose, formic acid, D-serine, adonitol, myo-inositol, L-lyxose and polysorbates. LPS from resistant organisms grown without colistin pressure lacked substitutions with 4-Amino-Arabinose or ethanolamine but was more structurally complex, with more molecular species present. Conclusions: Colistin resistance is frequent in the E. cloacae complex and increasing among bloodstream isolates. It is associated with: (i) particular genomic and metabolic clusters; (ii) identification as E. asburiae; and (iii) with more complex LPS architectures.