Although a variety of bacterial species have been reported to use the interspecies communication signal autoinducer-2 (AI-2) to regulate multiple behaviors, the molecular mechanisms of AI-2 recognition and signal transduction remain poorly understood. To date, two types of AI-2 receptors have been identified: LuxP, present in Vibrio spp., and LsrB, first identified in Salmonella enterica serovar Typhimurium. In S. Typhimurium, LsrB is the ligand binding protein of a transport system that enables the internalization of AI-2. Here, using both sequence analysis and structure prediction, we establish a set of criteria for identifying functional AI-2 receptors. We test our predictions experimentally, assaying key species for their abilities to import AI-2 in vivo, and test their LsrB orthologs for AI-2 binding in vitro. Using these experimental approaches, we were able to identify AI-2 receptors in organisms belonging to phylogenetically distinct families such as the Enterobacteriaceae, Rhizobiaceae, and Bacillaceae. Phylogenetic analysis of LsrB orthologs indicates that this pattern could result from one single origin of the functional LsrB gene in a gammaproteobacterium, suggesting possible posterior independent events of lateral gene transfer to the Alphaproteobacteria and Firmicutes. Finally, we used mutagenesis to show that two AI-2-interacting residues are essential for the AI-2 binding ability. These two residues are conserved in the binding sites of all the functional AI-2 binding proteins but not in the non-AI-2-binding orthologs. Together, these results strongly support our ability to identify functional LsrB-type AI-2 receptors, an important step in investigations of this interspecies signal.