mRNA levels are determined by the balance between transcription and mRNA degradation, and while transcription has been extensively studied, very little is known regarding the regulation of mRNA degradation and its coordination with transcription. Here we examine the evolution of mRNA degradation rates between two closely related yeast species. Surprisingly, we find that around half of the evolutionary changes in mRNA degradation were coupled to transcriptional changes that exert opposite effects on mRNA levels. Analysis of mRNA degradation rates in an interspecific hybrid further suggests that opposite evolutionary changes in transcription and in mRNA degradation are mechanistically coupled and were generated by the same individual mutations. Coupled changes are associated with divergence of two complexes that were previously implicated both in transcription and in mRNA degradation (Rpb4/7 and Ccr4-Not), as well as with sequence divergence of transcription factor binding motifs. These results suggest that an opposite coupling between the regulation of transcription and that of mRNA degradation has shaped the evolution of gene regulation in yeast.