5′-Methylthioadenosine nucleosidase (MTAN) is a bacterial enzyme involved in S-adenosylmethionine-related quorum sensing pathways that induce bacterial pathogenesis factors. Transition state analogues 5′-methylthio- (MT-), 5′-ethylthio- (EtT-) and 5′-butylthio- (BuT-) DADMe-ImmucillinAs are slow-onset, tight-binding inhibitors of Vibrio cholerae MTAN ( VcMTAN), with dissociation constants of 73, 70, and 208 pM, respectively. Structural analysis of VcMTAN with BuT-DADMe-ImmucillinA reveals interactions contributing to the high affinity. 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-ImmucillinA, disrupting autoinducer production in a dose-dependent manner without affecting growth. MT- and BuT-DADMe-ImmucillinA also inhibit autoinducer-2 production in enterohemorrhagic Escherichia coli O157:H7 with IC 50 values of 600, and 125 nM, respectively. BuT-DADMe-ImmucillinA inhibition of autoinducer-2 production in both strains persists for several generations, and causes reduction in biofilm formation. These results support MTAN’s role in quorum sensing, and its potential as target for bacterial anti-infective drug design.