Multidrug resistance in Pseudomonas aeruginosa is increasingly becoming a threat for human health. Indeed, some strains are resistant to almost all currently available antibiotics, leaving very limited choices for antimicrobial therapy. In many such cases, polymyxins are the only available option, although as their utilization increases so does the isolation of resistant strains. In this study, we screened a comprehensive PA14 mutant library to identify genes involved in changes of susceptibility to polymyxin B in P. aeruginosa. Surprisingly, our screening revealed that the polymyxin B resistome of this microorganism is fairly small. Thus, only one resistant mutant and 17 different susceptibility/intrinsic resistance determinants were identified. Among the susceptible mutants, a significant number carried transposon insertions in lipopolysaccharide (LPS)-related genes. LPS analysis revealed that four of these mutants (galU, lptC, wapR, and ssg) had an altered banding profile in SDS-polyacrylamide gels and Western blots, with three of them exhibiting LPS core truncation and lack of O-antigen decoration. Further characterization of these four mutants showed that their increased susceptibility to polymyxin B was partly due to increased basal outer membrane permeability. Additionally, these mutants also lacked the aminoarabinose-substituted lipid A species observed in the wild type upon growth in low magnesium. Overall, our results emphasize the importance of LPS integrity and lipid A modification in resistance to polymyxins in P. aeruginosa, highlighting the relevance of characterizing the genes that affect biosynthesis of cell surface structures in this pathogen to follow the evolution of peptide resistance in the clinic.