The extracellular signaling molecule autoinducer-2 (AI-2) mediates quorum-sensing communication in diverse bacterial species. In marine vibrios, binding of AI-2 to the periplasmic receptor LuxP modulates the activity of the inner membrane sensor kinase LuxQ, transducing the AI-2 information into the cytoplasm. Here, we show that Vibrio harveyi LuxP associates with LuxQ in both the presence and absence of AI-2. The 1.9 A X-ray crystal structure of apoLuxP, complexed with the periplasmic domain of LuxQ, reveals that the latter contains two tandem Per/ARNT/Simple-minded (PAS) folds. Thus, although many prokaryotic PAS folds themselves bind ligands, the LuxQ periplasmic PAS folds instead bind LuxP, monitoring its AI-2 occupancy. Mutations that disrupt the apoLuxP:LuxQ interface sensitize V. harveyi to AI-2, implying that AI-2 binding causes the replacement of one set of LuxP:LuxQ contacts with another. These conformational changes switch LuxQ between two opposing enzymatic activities, each of which conveys information to the cytoplasm about the cell density of the surrounding environment.