Cellular responses to environmental stress are frequently mediated by RNA-binding proteins (RBPs). Here, we examined global RBP dynamics in Saccharomyces cerevisiae in response to glucose starvation and heat shock. Each stress induced rapid remodeling of the protein:RNA interactome, without corresponding changes in RBP abundance. Consistent with general translation shutdown, ribosomal proteins contacting the mRNA showed decreased RNA-association. Among translation components, RNA-association was most reduced for initiation factors involved in 40S scanning (eIF4A, eIF4B, and Ded1), indicating a common mechanism of translational repression. In unstressed cells, eIF4A, eIF4B, and Ded1 primarily targeted the 5′-ends of mRNAs. Following glucose withdrawal, mRNAs remained stable, but 5’-binding was abolished within 30sec, explaining the rapid translation shutdown. Heat shock induced progressive loss of 5’ RNA-binding by initiation factors over ~16min, and translation shutoff provoked 5′-degradation by Xrn1, selectively for mRNAs encoding translation-related factors. These results reveal mechanisms underlying translational control of gene expression during stress.