The bacterial DNA sliding clamp (SC), or replication processivity factor, is a promising target for the development of novel antibiotics. We report a structure–activity relationship study of a new series of peptides interacting within the Escherichia coli SC (^EcSC) binding pocket. Various modifications were explored including N-alkylation of the peptide bonds, extension of the N-terminal moiety, and introduction of hydrophobic and constrained residues at the C-terminus. In each category, single modifications were identified that increased affinity to ^EcSC. A combination of such modifications yielded in several cases to a substantially increased affinity compared to the parent peptides with K_d in the range of 30–80 nM. X-ray structure analysis of 11 peptide/^EcSC co-crystals revealed new interactions at the peptide-protein interface (i.e., stacking interactions, hydrogen bonds, and hydrophobic contacts) that can account for the improved binding. Several compounds among the best binders were also found to be more effective in inhibiting SC-dependent DNA synthesis.