ABSTRACT Stable protein complexes, including those formed with RNA, are major building blocks of every living cell. Escherichia coli has been the leading bacterial organism with respect to global protein-protein networks. Yet, there has been no global census of RNA/protein complexes in this model species of microbiology. Here, we performed Grad-seq to establish an RNA/protein complexome, reconstructing sedimentation profiles in a glycerol gradient for ~85% of all E. coli transcripts and ~49% of the proteins. These include the majority of small noncoding RNAs (sRNAs) detectable in this bacterium as well as the general sRNA-binding proteins, CsrA, Hfq and ProQ. In presenting use cases for utilization of these RNA and protein maps, we show that a stable association of RyeG with 30S ribosomes gives this seemingly noncoding RNA of prophage origin away as an mRNA of a toxic small protein. Similarly, we show that the broadly conserved uncharacterized protein YggL is a 50S subunit factor in assembled 70S ribosomes. Overall, this study crucially extends our knowledge about the cellular interactome of the primary model bacterium E. coli through providing global RNA/protein complexome information and should facilitate functional discovery in this and related species.