Infections by multidrug-resistant Gram-negative bacteria are increasingly common, prompting the renewed interest in the use of colistin. Colistin specifically targets Gram-negative bacteria by interacting with the anionic lipid A moieties of lipopolysaccharides, leading to membrane destabilization and cell death. Here, we aimed to uncover the mechanisms of colistin resistance in nine colistin-resistant Escherichia coli strains and one Escherichia albertii strain. These were the only colistin-resistant strains of 1,140 bloodstream Escherichia isolates collected in a tertiary hospital over a 10-year period (2006 to 2015). Core-genome phylogenetic analysis showed that each patient was colonized by a unique strain, suggesting that colistin resistance was acquired independently in each strain. All colistin-resistant strains had lipid A that was modified with phosphoethanolamine. In addition, two E. coli strains had hepta-acylated lipid A species, containing an additional palmitate compared to the canonical hexa-acylated E. coli lipid A. One E. coli strain carried the mobile colistin resistance (mcr) gene mcr-1.1 on an IncX4-type plasmid. Through construction of chromosomal transgene integration mutants, we experimentally determined that mutations in basRS, encoding a two-component signal transduction system, contributed to colistin resistance in four strains. We confirmed these observations by reversing the mutations in basRS to the sequences found in reference strains, resulting in loss of colistin resistance. While the mcr genes have become a widely studied mechanism of colistin resistance in E. coli, sequence variation in basRS is another, potentially more prevalent but relatively underexplored, cause of colistin resistance in this important nosocomial pathogen.IMPORTANCE Multidrug resistance among Gram-negative bacteria has led to the use of colistin as a last-resort drug. The cationic colistin kills Gram-negative bacteria through electrostatic interaction with the anionic lipid A moiety of lipopolysaccharides. Due to increased use in clinical and agricultural settings, colistin resistance has recently started to emerge. In this study, we used a combination of whole-genome sequence analysis and experimental validation to characterize the mechanisms through which Escherichia coli strains from bloodstream infections can develop colistin resistance. We found no evidence of direct transfer of colistin-resistant isolates between patients. The lipid A of all isolates was modified by the addition of phosphoethanolamine. In four isolates, colistin resistance was experimentally verified to be caused by mutations in the basRS genes, encoding a two-component regulatory system. Our data show that chromosomal mutations are an important cause of colistin resistance among clinical E. coli isolates.