Many pathogenic bacteria utilize the type III secretion system (T3SS) to translocate effector proteins directly into host cells, facilitating colonization. In enterohemmorhagic Escherichia coli (EHEC), a subset of T3SS effectors is essential for suppression of the inflammatory response in hosts, including humans. Identified as a zinc protease that cleaves NF-κB transcription factors, NleC is one such effector. Here, we investigate NleC substrate specificity, showing that four residues around the cleavage site in the DNA-binding loop of the NF-κB subunit RelA strongly influence the cleavage rate. Class I NF-κB subunit p50 is cleaved at a reduced rate consistent with conservation of only three of these four residues. However, peptides containing 10 residues on each side of the scissile bond were not efficiently cleaved by NleC, indicating that elements distal from the cleavage site are also important for substrate recognition. We present the crystal structure of NleC and show that it mimics DNA structurally and electrostatically. Consistent with this model, mutation of phosphate-mimicking residues in NleC reduces the level of RelA cleavage. We propose that global recognition of NF-κB subunits by DNA mimicry combined with a high sequence selectivity for the cleavage site results in exquisite NleC substrate specificity. The structure also shows that despite undetectable similarity of its sequence to those of other Zn(2+) proteases beyond its conserved HExxH Zn(2+)-binding motif, NleC is a member of the Zincin protease superfamily, albeit divergent from its structural homologues. In particular, NleC displays a modified Ψ-loop motif that may be important for folding and refolding requirements implicit in T3SS translocation.