Peptide deformylase catalyzes the removal of the N-terminal formyl group from nascent polypeptides during prokaryotic protein synthesis and maturation and is essential for bacterial survival. Its apparent absence from mammalian organisms makes it an attractive target for designing novel antibacterial agents. Based on the substrate specificity of peptide deformylase from Escherichia coli, a focused library of peptide thiols was synthesized on TentaGel resin using a disulfide linkage. Screening of the library against the purified deformylase was carried out in solution phase after the inhibitors were released from the resin with a reducing agent. A potent deformylase inhibitor was obtained from a 750-member library and was further optimized through rational modification into a low nanomolar inhibitor (KI = 15 nM against E. coli deformylase).