Upon infection of epithelial cells, enteropathogenic Escherichia coli suppresses host cell inflammatory signalling in a type III secretion system (T3SS) dependent manner. Two key T3SS effector proteins involved in this response are NleE and NleC. NleC is a zinc metalloprotease effector that degrades the p65 subunit of NF-κB. Although the site of p65 cleavage by NleC is now well described, other areas of interaction have not been precisely defined. Here we constructed overlapping truncations of p65 to identify regions required for NleC cleavage. We determined that NleC cleaved both p65 and p50 within the Rel homology domain (RHD) and that two motifs, E22IIE25 and P177VLS180 , within the RHD of p65 were important for recognition and binding by NleC. Alanine substitution of one or both of these motifs protected p65 from binding and degradation by NleC. The E22IIE25 and P177VLS180 motifs were located within the structurally distinct N-terminal subdomain of the RHD involved in DNA binding by p65 on adjacent, parallel strands. Although these motifs have not been recognized previously, both were needed for the correct localization and function of p65. In summary, this work has identified two regions of p65 within the RHD needed for binding and cleavage by NleC and provides further insight into the molecular basis of substrate recognition by a T3SS effector.