One mechanism by which bacteria survive environmental stress is through the formation of bacterial persisters, a sub-population of genetically identical quiescent cells that exhibit multidrug tolerance and are highly enriched in bacterial toxins. Recently, the Escherichia coli gene mqsR (b3022) was identified as the gene most highly upregulated in persisters. Here, we report multiple individual and complex three-dimensional structures of MqsR and its antitoxin MqsA (B3021), which reveal that MqsR:MqsA form a novel toxin:antitoxin (TA) pair. MqsR adopts an alpha/beta fold that is homologous with the RelE/YoeB family of bacterial ribonuclease toxins. MqsA is an elongated dimer that neutralizes MqsR toxicity. As expected for a TA pair, MqsA binds its own promoter. Unexpectedly, it also binds the promoters of genes important for E. coli physiology (e.g., mcbR, spy). Unlike canonical antitoxins, MqsA is also structured throughout its entire sequence, binds zinc and coordinates DNA via its C- and not N-terminal domain. These studies reveal that TA systems, especially the antitoxins, are significantly more diverse than previously recognized and provide new insights into the role of toxins in maintaining the persister state.