A previously developed method for cyclic peptide synthesis was demonstrated to be able to provide convenient access to large combinatorial libraries of analogues, and this methodology was applied to the optimization of natural product cyclic decapeptides. Using this method, a 192-member library was designed and successfully constructed on the basis of the natural products tyrocidines, streptocidins, and loloatins to increase the therapeutic indices of these antibiotics. Library screening identified nine analogues whose therapeutic indices were increased by up to 90-fold in comparison to the natural products. Three of these analogues showed significant increase in antibacterial potency and concurrent drastic decrease in hemolytic activity. Since the natural products target the bacterial cell wall, the newly discovered analogues are promising leads for drug development against drug-resistant bacteria.