Antimicrobial resistance among Gram-negative bacteria is a growing problem, fueled by the paucity of new antibiotics that target these microorganisms. One novel family of macrocyclic β-hairpin-shaped peptidomimetics was recently shown to act specifically against Pseudomonas spp. by a novel mechanism of action, targeting the outer membrane protein LptD, which mediates lipopolysaccharide transport to the cell surface during outer membrane biogenesis. Here we explore the mode of binding of one of these β-hairpin peptidomimetics to LptD in Pseudomonas aeruginosa, by examining the effects on antimicrobial activity following N-methylation of individual peptide bonds. An N-methyl scan of the cyclic peptide revealed that residues on both sides of the β-hairpin structure at a non-hydrogen bonding position likely mediate hydrogen-bonding interactions with the target LptD. Structural analyses by NMR spectroscopy further reinforce the conclusion that the folded β-hairpin structure of the peptidomimetic is critical for binding to the target LptD. Finally, new NMe analogues with potent activity have been identified, which opens new avenues for optimization in this family of antimicrobial peptides.