Numerous proteins regulate gene expression by modulating mRNA translation and decay. In order to uncover the full scope of these post-transcriptional regulators, we conducted an unbiased survey that quantifies regulatory activity across the budding yeast proteome and delineates the protein domains responsible for these effects. Our approach couples a tethered function assay with quantitative single-cell fluorescence measurements to analyze ~50,000 protein fragments and determine their effects on a tethered mRNA. We characterize hundreds of strong regulators, which are enriched for canonical and unconventional mRNA-binding proteins. Regulatory activity typically maps outside the RNA-binding domains themselves, highlighting a modular architecture that separates mRNA targeting from post-transcriptional regulation. Activity often aligns with intrinsically disordered regions that can interact with other proteins, even in core mRNA translation and degradation factors. Our results thus reveal networks of interacting proteins that control mRNA fate and illuminate the molecular basis for post-transcriptional gene regulation.