In the present report we characterized the outer membrane proteome, genomic, and lipid A remodelling changes following the evolution of a colistin-susceptible K. pneumoniae ATCC 13883 strain into an extremely colistin-resistant strain. Lipid A profiling revealed the outer membrane of the colistin-susceptible strain is decorated primarily by hexa- and hepta-acylated lipid A species and a minor tetra-acylated species. In the lipid A profile of the extremely colistin-resistant strain, in addition to the aforementioned lipid A species, the obligatory 4-amino-4-deoxy-l-arabinose modification of the hexa-acylated lipid A was detected. Comparative genomic analysis revealed that the mgrB gene of the colistin-resistant strain is inactivated by a single nucleotide insertion which produces a frame-shift, resulting in premature termination. We also detected two synonymous mutations in the two-component system genes phoP and phoQ. Comparative profiling of the outer membrane proteome of each strain revealed that outer membrane proteins from bacterial stress response, glutamine degradation, pyruvate, aspartate, and asparagine metabolic pathways were over-represented in the extremely colistin-resistant K. pneumoniae ATCC 13883 strain. In comparison, in the sensitive strain, outer membrane proteins from carbohydrate metabolism, H-ATPase, cell division, and peptidoglycan biosynthesis were over-represented. Notably, there were no discernible differences between the OmpK35 and OmpK36 major outer membrane porins between the polymyxin-susceptible and -resistant strains suggesting porin deficiency is not involved in the colistin resistance in the ATCC 13883 strain. These findings shed new light on the outer membrane remodelling events accompanying the development of extremely high levels of colistin resistance in K. pneumoniae.