In the light of occurrence of bacterial strains with multiple resistances against most antibiotics, antimicrobial peptides that interact with the outer layer of Gram-negative bacteria, such as polymyxin (PMX), have recently received increased attention. Here we present a study of the interactions of PMX-B, -E, and -M with lipopolysaccharide (LPS) from a deep rough mutant strain of Escherichia coli. A method for efficient purification of biosynthetically produced LPS using reversed-phase high-performance liquid chromatography in combination with ternary solvent mixtures was developed. LPS was incorporated into a membrane model, dodecylphosphocholine micelles, and its interaction with polymyxins was studied by heteronuclear NMR spectroscopy. Data from chemical shift mapping using isotope-labeled LPS or labeled polymyxin, as well as from isotope-filtered nuclear Overhauser effect spectroscopy experiments, reveal the mode of interaction of LPS with polymyxins. Using molecular dynamics calculations the complex of LPS with PMX-B in the presence of dodecylphosphocholine micelles was modeled using restraints derived from chemical shift mapping data and intermolecular nuclear Overhauser effects. In the modeled complex the macrocycle of PMX is centered around the phosphate group at GlcN-B, and additional contacts from polar side chains are formed to GlcN-A and Kdo-C, whereas hydrophobic side chains penetrate the acyl-chain region.