Polymyxin, a long-known peptide antibiotic, has recently been reintroduced in clinical practice because it is sometimes the only available antibiotic for the treatment of multidrug-resistant gram-negative pathogenic bacteria. Lack of information on the biosynthetic genes of polymyxin, however, has limited the study of structure-function relationships and the development of improved polymyxins. During whole genome sequencing of Paenibacillus polymyxa E681, a plant growth-promoting rhizobacterium, we identified a gene cluster encoding polymyxin synthetase. Here, we report the complete sequence of the gene cluster and its function in polymyxin biosynthesis. The gene cluster spanning the 40.6-kb region consists of five open reading frames, designated pmxA, pmxB, pmxC, pmxD, and pmxE. The pmxC and pmxD genes are similar to genes that encode transport proteins, while pmxA, pmxB, and pmxE encode polymyxin synthetases. The insertional disruption of pmxE led to a loss of the ability to produce polymyxin. Introduction of the pmx gene cluster into the amyE locus of the Bacillus subtilis chromosome resulted in the production of polymyxin in the presence of extracellularly added L-2,4-diaminobutyric acid. Taken together, our findings demonstrate that the pmx gene cluster is responsible for polymyxin biosynthesis.