Enteropathogenic Escherichia coli (EPEC) utilises a type III secretion system (T3SS) to translocate effector proteins directly into enterocytes and subvert host cell signaling. Non-LEE encoded effector C (NleC) is one of a number of T3SS effectors which inhibit NF-κB signaling. The mechanism of action of NleC is unlike those of effectors such as NleE which inhibits NF-κB signaling upstream of NF-κB proteins. NleC acts directly on the NF-κB protein p65 by cleaving it and preventing inflammatory cytokine production to allow EPEC to persist within the host. Analysis of the amino acid sequence of NleC reveals it contains the zinc metalloprotease consensus motif HEXXH, and mutation of this motif abrogates NleC function. While the NleC cleavage site within p65 is well established, not much is known about how NleC recognizes its substrates. In this study we co-expressed truncations of p65 with NleC ectopically in HeLa cells to determine the minimal region of p65 required for cleavage by NleC. We determined that NleC cleaved both p65 and p50 within the conserved 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. These motifs were also essential for p65 function and localisation, as upon their mutation, p65 formed puncate nuclear structures and localised to PML nuclear bodies, which are involved in stress responses and can be a site for p65 degradation. The PML nuclear body is extensively studied because of its involvement in tumour suppression, however there is debate over its precise role. The p65 mutants identified in this study could be useful for investigating the interaction of PML nuclear bodies with p65, which is not well understood.