Genes encoding toxin-antitoxin (TA) systems are near ubiquitous in bacterial genomes and they play key roles in important aspects of bacterial physiology, including genomic stability, formation of persister cells under antibiotic stress, and resistance to phage infection. The CptIN locus from Eubacterium rectale is a member of the recently-discovered Type III class of TA systems, defined by a protein toxin suppressed by direct interaction with a structured RNA antitoxin. Here, we present the crystal structure of the CptIN protein-RNA complex to 2.2 Å resolution. The structure reveals a new heterotetrameric quaternary organization for the Type III TA class, and the RNA antitoxin bears a novel structural feature of an extended A-twist motif within the pseudoknot fold. The retention of a conserved ribonuclease active site as well as traits normally associated with TA systems, such as plasmid maintenance, implicates a wider functional role for Type III TA systems. We present evidence for the co-variation of the Type III component pair, highlighting a distinctive evolutionary process in which an enzyme and its substrate co-evolve.