In contrast to Escherichia coli, a model organism for chemotaxis that has 5 chemoreceptors and a single chemosensory pathway, Pseudomonas aeruginosa PAO1 has a much more complex chemosensory network, which consists of 26 chemoreceptors feeding into four chemosensory pathways. While several chemoreceptors were rigorously linked to specific pathways in a series of experimental studies, for most of them this information is not available. Thus, we addressed the problem computationally. Protein–protein interaction network prediction, coexpression data mining, and phylogenetic profiling all produced incomplete and uncertain assignments of chemoreceptors to pathways. However, comparative sequence analysis specifically targeting chemoreceptor regions involved in pathway interactions revealed conserved sequence patterns that enabled us to unambiguously link all 26 chemoreceptors to four pathways. Placing computational evidence in the context of experimental data allowed us to conclude that three chemosensory pathways in P. aeruginosa utilize one chemoreceptor per pathway, whereas the fourth pathway, which is the main system controlling chemotaxis, utilizes the other 23 chemoreceptors. Our results show that while only a very few amino acid positions in receptors, kinases, and adaptors determine their pathway specificity, assigning receptors to pathways computationally is possible. This requires substantial knowledge about interacting partners on a molecular level and focusing comparative sequence analysis on the pathway-specific regions. This general principle should be applicable to resolving many other receptor–pathway interactions.