Bacterial populations use cell-cell communication to coordinate community-wide regulation of processes such as biofilm formation, virulence, and bioluminescence. This phenomenon, termed quorum sensing, is mediated by small molecule signals known as autoinducers. While most autoinducers are species specific, autoinducer-2 (AI-2), first identified in the marine bacterium Vibrio harveyi, is produced and detected by many Gram-negative and Gram-positive bacteria. The crystal structure of the V. harveyi AI-2 signaling molecule bound to its receptor protein revealed an unusual furanosyl borate diester. Here, we present the crystal structure of a second AI-2 signal binding protein, LsrB from Salmonella typhimurium. We find that LsrB binds a chemically distinct form of the AI-2 signal, (2R,4S)-2-methyl-2,3,3,4-tetrahydroxytetrahydrofuran (R-THMF), that lacks boron. Our results demonstrate that two different species of bacteria recognize two different forms of the autoinducer signal, both derived from 4,5-dihydroxy-2,3-pentanedione (DPD), and reveal new sophistication in the chemical lexicon used by bacteria in interspecies signaling.