Type I signal peptidases are potential targets for the development of new antibacterial agents. Here we report finding potent inhibitors of E. coli type I signal peptidase (LepB), by optimizing a previously reported hit compound, decanoyl-PTANA-CHO, through modifications at the N- and C-termini. Good improvements of inhibitory potency were obtained, with IC50s in the low nanomolar range. The best inhibitors also showed good antimicrobial activity, with MICs in the low μg/mL range for several bacterial species. The selection of resistant mutants provided strong support for LepB as the target of these compounds. The cytotoxicity and hemolytic profiles of these compounds are not optimal but the finding that minor structural changes cause the large effects on these properties suggests that there is potential for optimization in future studies.