5'-Methylthioadenosine/S-adenosylhomocysteine nucleosidase (MTAN) is a bacterial enzyme involved in S-adenosylmethionine-related quorum sensing pathways that induce bacterial pathogenesis factors. Transition state analogs MT-DADMe-Immucillin-A, EtT-DADMe-Immucillin-A and BuT-DADMe-Immucillin-A are slow-onset, tight-binding inhibitors of Vibrio cholerae MTAN (VcMTAN), with equilibrium dissociation constants of 73, 70 and 208 pM, respectively. Structural analysis of VcMTAN with BuT-DADMe-Immucillin-A revealed interactions contributing to the high affinity. We found that in V. cholerae cells, these compounds are potent MTAN inhibitors with IC(50) values of 27, 31 and 6 nM for MT-, EtT- and BuT-DADMe-Immucillin-A, respectively; the compounds disrupt autoinducer production in a dose-dependent manner without affecting growth. MT- and BuT-DADMe-Immucillin-A also inhibited autoinducer-2 production in enterohemorrhagic Escherichia coli O157:H7 with IC(50) values of 600 and 125 nM, respectively. BuT-DADMe-Immucillin-A inhibition of autoinducer-2 production in both strains persisted for several generations and caused reduction in biofilm formation. These results support MTAN's role in quorum sensing and its potential as a target for bacterial anti-infective drug design.