Type II toxin-antitoxin (TA) systems are considered as protein pairs in which a specific toxin is associated with a specific antitoxin. We have identified a novel antitoxin family (paaA) that is associated with parE toxins. The paaA-parE gene pairs form an operon with a third component (paaR) encoding a transcriptional regulator. Two paralogous paaR-paaA-parE systems are found in E. coli O157:H7. Deletions of the paaA-parE pairs in O157:H7 allowed us to show that these systems are expressed in their natural host and that PaaA antitoxins specifically counteract toxicity of their associated ParE toxin. For the paaR2-paaA2-parE2 system, PaaR2 and Paa2-ParE2 complex are able to regulate the operon expression and both are necessary to ensure complete repression. The paaR2-paaA2-parE2 system mediates ClpXP-dependent post-segregational killing. The PaaR2 regulator appears to be essential for this function, most likely by maintaining an appropriate antitoxin : toxin ratio in steady-state conditions. Ectopic overexpression of ParE2 is bactericidal and is not resuscitated by PaaA2 expression. ParE2 colocalizes with the nucleoid, while it is diffusely distributed in the cytoplasm when PaaA2 is coexpressed. This indicates that ParE2 interacts with DNA-gyrase cycling on DNA and that coexpression of PaaA2 antitoxin sequesters ParE2 away from its target by protein-protein complex formation.