The interaction of antimicrobial peptides (AMPs) with the inner membrane of Gram-negative bacteria is a key determinant of their abilities to exert diverse bactericidal effects. Here we present a molecular level understanding of the initial target membrane interaction for two cationic α-helical AMPs that share structural similarities but have a ten-fold difference in antibacterial potency towards Gram-negative bacteria. The binding and insertion from solution of pleurocidin or magainin 2 to membranes representing the inner membrane of Gram-negative bacteria, comprising a mixture of 128 anionic and 384 zwitterionic lipids, is monitored over 100 ns in all atom molecular dynamics simulations. The effects of the membrane interaction on both the peptide and lipid constituents are considered and compared with new and published experimental data obtained in the steady state. While both magainin 2 and pleurocidin are capable of disrupting bacterial membranes, the greater potency of pleurocidin is linked to its ability to penetrate within the bacterial cell. We show that pleurocidin displays much greater conformational flexibility when compared with magainin 2, resists self-association at the membrane surface and penetrates further into the hydrophobic core of the lipid bilayer. Conformational flexibility is therefore revealed as a key feature required of apparently α-helical cationic AMPs for enhanced antibacterial potency.