Many bacterial pathogens modulate their metabolic activity, virulence and pathogenicity through so-called "toxin-antitoxin" (TA) modules. The genome of the human pathogen Escherichia coli O157 contains two three-component TA modules related to the known parDE module. Here, we show that the toxin EcParE2 maps in a branch of the RelE/ParE toxin superfamily that is distinct from the branches that contain verified gyrase and ribosome inhibitors. The structure of EcParE2 closely resembles that of Caulobacter crescentus ParE but shows a distinct pattern of conserved surface residues, in agreement with its apparent inability to interact with GyrA. The antitoxin EcPaaA2 is characterized by two α-helices (H1 and H2) that serve as molecular recognition elements to wrap itself around EcParE2. Both EcPaaA2 H1 and H2 are required to sustain a high-affinity interaction with EcParE2 and for the inhibition of EcParE2-mediated killing in vivo. Furthermore, evidence demonstrates that EcPaaA2 H2, but not H1, determines specificity for EcParE2. The initially formed EcPaaA2-EcParE2 heterodimer then assembles into a hetero-hexadecamer, which is stable in solution and is formed in a highly cooperative manner. Together these findings provide novel data on quaternary structure, TA interactions and activity of a hitherto poorly characterized family of TA modules.