Pseudomonas aeruginosa is an opportunistic human pathogen and a leading cause of nosocomial infections. Due to its high intrinsic and adaptive resistance to antibiotics, infections caused by this organism are difficult to treat and new therapeutic options are urgently needed. Novel peptidomimetic antibiotics that target outer membrane (OM) proteins have shown great promise for the treatment of P. aeruginosa infections. Here, we have performed genome-wide mutant fitness profiling using transposon sequencing (Tn-Seq) to identify resistance determinants against the recently described peptidomimetics L27-11, compounds 3 and 4, as well as polymyxin B2 (PMB) and colistin (COL). We identified a set of 13 core genes that affected resistance to all tested antibiotics, many of which encode enzymes involved in the modification of the lipopolysaccharide (LPS) or control their expression. We also identified fitness determinants that are specific for antibiotics with similar structures that may indicate differences in their modes of action. These results provide new insights into resistance mechanisms against these peptide antibiotics, which will be important for future clinical development and efforts to further improve their potency.