The worldwide prevalence of infections caused by antibiotic-resistant Gram-negative bacteria poses a serious threat to public health due to the limited therapeutic alternatives. Cationic peptides represent a large family of antibiotics and have attracted interest due to their diverse chemical structures and potential for combating drug-resistant Gram-negative pathogens. Here, we analyze 7395 bacterial genomes to investigate their capacity for biosynthesis of cationic nonribosomal peptides with activity against Gram-negative bacteria. Applying this approach, we identify two novel compounds (brevicidine and laterocidine) showing bactericidal activities against antibiotic-resistant Gram-negative pathogens, such as Pseudomonas aeruginosa and colistin-resistant Escherichia coli, and an apparently low risk of resistance. The two peptides show efficacy against E. coli in a mouse thigh infection model. These findings may contribute to the discovery and development of Gram-negative antibiotics.