TldD and TldE proteins are involved in the biosynthesis of microcin B17 (MccB17), an Escherichia coli thiazole/oxazole-modified peptide toxin targeting DNA gyrase. Using a combination of biochemical and crystallographic methods we show that E. coli TldD and TldE interact to form a heterodimeric metalloprotease. TldD/E cleaves the N-terminal leader sequence from the modified MccB17 precursor peptide, to yield mature antibiotic, while it has no effect on the unmodified peptide. Both proteins are essential for the activity; however, only the TldD subunit forms a novel metal-containing active site within the hollow core of the heterodimer. Peptide substrates are bound in a sequence-independent manner through ß sheet interactions with TldD and are likely cleaved via a thermolysin-type mechanism. We suggest that TldD/E acts as a "molecular pencil sharpener": unfolded polypeptides are fed through a narrow channel into the active site and processively truncated through the cleavage of short peptides from the N-terminal end.