Although distinct amino acid motifs containing consecutive prolines (polyP) cause ribosome stalling, which necessitates recruitment of the translation elongation factor P (EF-P), they occur strikingly often in bacterial proteomes. For example, polyP motifs are found in more than half of all histidine kinases in Escherichia coli K-12, which raises the question of their role(s) in receptor function. Here we have investigated the roles of two polyP motifs in the osmosensor and histidine kinase EnvZ. We show that the IPPPL motif in the HAMP domain is required for dimerization of EnvZ. Moreover, replacement of the prolines in this motif by alanines disables the receptor’s sensor function. The second motif, VVPPA, which is located in the periplasmic domain, was found to be required for interaction with the modulator protein MzrA. Our study also reveals that polyP-dependent stalling has little effect on EnvZ levels. Hence, both polyP motifs in EnvZ are primarily involved in protein-protein interaction. Furthermore, while the first motif occurs in almost all EnvZ homologues, the second motif is only found in species that have MzrA, indicating co-evolution of the two proteins.