Inorganic phosphate (Pi) is a central signaling molecule that modulates virulence in various pathogens. In Pseudomonas aeruginosa, low Pi concentrations induce transcriptional alterations that increase virulence. Also, under low Pi levels, P. aeruginosa exhibits Pi chemotaxis-a process mediated by the two non-paralogous receptors CtpH and CtpL. Here we show that the two receptors operate via different mechanisms. We demonstrate that the ligand binding domain (LBD) of CtpH but not CtpL binds Pi directly. We identify the periplasmic ligand binding protein PstS as the protein that binds in its Pi loaded state to CtpL, resulting in receptor stimulation. PstS forms part of the Pi transporter and has thus a double function in Pi transport and chemotaxis. The affinity of Pi for CtpH was modest whereas that for PstS very high, which may explain why CtpH and CtpL mediate chemotaxis to high and low Pi concentrations, respectively. The pstS/ctpH double mutant was almost devoid of Pi taxis, indicating that PstS is the only CtpL Pi-shuttle. Chemotaxis mechanisms based on indirect ligand recognition were unambiguously identified in enterobacteria. The discovery of a similar mechanism in a different bacterial order, involving a different chemoreceptor type and chemoeffector suggests that such systems are widespread.