The closely related type III secretion system zinc metalloprotease effector proteins GtgA, GogA, and PipA are translocated into host cells during Salmonella infection. They then cleave nuclear factor κ-light-chain-enhancer of activated B cells (NF-κB) transcription factor subunits, dampening activation of the NF-κB signaling pathway and thereby suppressing host immune responses. We demonstrate here that GtgA, GogA, and PipA cleave a subset of NF-κB subunits, including p65, RelB, and cRel but not NF-κB1 and NF-κB2, whereas the functionally similar type III secretion system effector NleC of enteropathogenic and enterohemorrhagic Escherichia coli cleaved all five NF-κB subunits. Mutational analysis of NF-κB subunits revealed that a single nonconserved residue in NF-κB1 and NF-κB2 that corresponds to the P1′ residue Arg-41 in p65 prevents cleavage of these subunits by GtgA, GogA, and PipA, explaining the observed substrate specificity of these enzymes. Crystal structures of GtgA in its apo-form and in complex with the p65 N-terminal domain explained the importance of the P1′ residue. Furthermore, the pattern of interactions suggested that GtgA recognizes NF-κB subunits by mimicking the shape and negative charge of the DNA phosphate backbone. Moreover, structure-based mutational analysis of GtgA uncovered amino acids that are required for the interaction of GtgA with p65, as well as those that are required for full activity of GtgA in suppressing NF-κB activation. This study therefore provides detailed and critical insight into the mechanism of substrate recognition by this family of proteins important for bacterial virulence.