Small regulatory RNAs have been identified in a wide range of organisms, where they modify mRNA stability, translation or protein function. Small RNA regulators (sRNAs) either pair with mRNA targets or modify protein activities. Here we discuss current knowledge of the various proteins that interact with RNA regulators and review the physiologic implications of sRNA-protein complexes in DNA, RNA and protein metabolism, as well as in RNA and protein quality control in prokaryotes. Proteins that interact with the sRNAs can possess catalytic activity, induce conformational changes of the sRNA, or be sequestered by the sRNA to prevent the action of the protein.