Polymyxins are last-line antibiotics against life-threatening multidrug-resistant Gram-negative bacteria. Unfortunately, polymyxin resistance is increasingly reported, leaving a total lack of therapies. Using lipidomics and transcriptomics, we discovered that polymyxin B induced lipid A deacylation via pagL in both polymyxin-resistant and -susceptible Pseudomonas aeruginosa. Our results demonstrated that the deacylation of lipid A is an "innate immunity" response to polymyxins and a key compensatory mechanism to the aminoarabinose modification to confer high-level polymyxin resistance in P. aeruginosa. Furthermore, cutting-edge neutron reflectometry studies revealed that an assembled outer membrane (OM) with the less hydrophobic penta-acylated lipid A decreased polymyxin B penetration, compared to the hexa-acylated form. Polymyxin analogues with enhanced hydrophobicity displayed superior penetration into the tail regions of the penta-acylated lipid A OM. Our findings reveal a previously undiscovered mechanism of polymyxin resistance, wherein polymyxin-induced lipid A remodeling affects the OM packing and hydrophobicity, perturbs polymyxin penetration, and thereby confers high-level resistance.