In many bacteria, polyphosphate kinase (PPK) enzymes use ATP to synthesize polyphosphate (polyP) in response to cellular stress. These chains of inorganic phosphates are joined by high-energy bonds and can reach hundreds of residues in length. PolyP plays diverse functions in helping bacteria adjust to changing environmental conditions. However, the molecular mechanisms underlying these functions are poorly understood. In eukaryotic cells, polyacidic serine- and lysine-rich (PASK) motifs of proteins can mediate binding to polyP chains. Whereas PASK motifs are relatively common in yeast and human cells, we report that these sequences are rare in bacteria commonly used for polyP research. Thus, to identify novel polyP-binding proteins in Escherichia coli, we carried out a screen and identified seven novel targets with links to translation control and ribosome biogenesis. For two targets, the GTPase activating protein YihI and the ribonuclease Rnr, we mapped the regions of polyP interaction to non-PASK sequences and identified lysine residues critical for binding. We found that deletion of rnr suppressed the slow-growth phenotype of Δppk mutants grown on minimal media. Conversely, ppk deletion resulted in decreased Rnr protein expression. These phenotypes were dependent on the polyP-binding region of Rnr but independent of polyP binding itself, suggesting a complex interplay between PPK and Rnr function in E. coli. Overall, our work provides new insights into the scope of polyP-binding proteins and extends the connections between polyP and the regulation of protein translation in E. coli. IMPORTANCE: In bacteria, polyphosphate (polyP) molecules are important regulators of cellular stress responses. Accordingly, cells that cannot make polyP display defects in processes that are important for bacterial survival, infection, and antibiotic resistance. The molecular mechanisms by which polyP exerts its functions are poorly understood. In eukaryotic cells, there has been much interest in the identification and characterization of polyP-binding proteins that act as effectors of polyP in vivo. By comparison, much less is known about polyP-binding proteins in bacteria. In this study, we take advantage of large-scale collections of Escherichia coli strains expressing epitope-tagged proteins to carry out the first systematic search for bacterial polyP-binding proteins. We describe seven novel polyP-binding proteins with links to ribosome biogenesis or translation. We further identify a complex genetic and molecular interplay between polyphosphate kinase, the enzyme that makes polyP, and the polyP-binding protein RNase R. Given the importance of translational control for bacteria survival, investigation of these pathways is expected to reveal new targets that can be leveraged for therapeutic exploration.