The Mesorhizobium japonicum strain R7A symbiosis island ICEMlSymR7A is a 502-kb integrative and conjugative element that can undergo horizontal transfer to non-symbiotic mesorhizobia, making them capable of a nitrogen-fixing symbiosis with legumes. ICEMlSymR7A transfer is activated by TraR, a DNA-binding quorum-sensing activator that responds to N-acyl-homoserine lactones. TraR activates transcription of a second activator FseA, which in turn stimulates ICEMlSymR7A excision and conjugative transfer. In most R7A cells, quorum sensing and ICEMlSymR7A transfer are repressed by QseM, which binds both TraR and FseA. Here we present the NMR structure of QseM and reveal it comprises a novel helix-turn-helix (HTH) domain that has lost the ability to bind DNA. QseM shares homology with the C-terminal HTH domain of the transcriptional activator FseA. DNA-binding assays confirmed FseA binds the ICEMlSymR7A excisionase-gene promoter with nanomolar affinity. Amino-acid substitutions predicted to disrupt the DNA-binding interface of FseA abolished DNA binding, whilst substitutions in equivalent positions in QseM did not interfere with QseM function. Co-evolution and homology-modelling of FseA structure revealed a highly conserved N-terminal ‘WAWEFLRRN’ α-helix motif interfaces with the FseA C-terminal HTH domain. Bacterial two-hybrid assays showed QseM also bound and appeared to compete with the FseA HTH domain for this WAWEFLRRN α-helix. The ability of QseM to bind and inhibit FseA was destroyed by QseM substitutions at the predicted heterodimer interface. Interestingly, the same substitutions destroyed QseM's ability to bind and inhibit TraR, despite TraR sharing no primary-sequence similarity with FseA. Two-hybrid assays performed using truncated TraR variants revealed QseM binds the TraR AHL-binding domain. Moreover, fusion of the TraR AHL-binding domain to the LasR DNA-binding domain produced a functional chimeric quorum-sensing regulator that was repressible by QseM. In summary, QseM is a member of a novel family of HTH proteins that has lost the ability to bind DNA, retains an ability to inhibit a related transcriptional activator, and has additionally gained an ability to bind and inhibit an unrelated quorum-sensing regulator.