The vast number of noncoding RNAs in bacteria suggests that major post-transcriptional circuits beyond those controlled by the global RNA-binding proteins Hfq and CsrA may exist. To identify additional globally acting RNPs we have developed a method (gradient profiling by sequencing; Grad-seq) to partition the full ensemble of cellular RNAs based on their biochemical behavior. Consequently, we discovered transcripts that commonly interact with the osmoregulatory protein ProQ in Salmonella enterica. We show that ProQ is a conserved abundant RNA-binding protein with a wide range of targets, including a new class of ProQ-associated small RNAs that are highly structured and function to regulate mRNAs in trans. Based on its ability to chart the functional landscape of all cellular transcripts irrespective of their length and sequence diversity, Grad-seq promises to aid the discovery of major functional RNA classes and RNA-binding proteins in many organisms.