Post-transcriptional factors importantly contribute to the rapid and coordinated expression of the multiple genes required for the adaptation of living organisms to environmental stresses. In the model eukaryote Saccharomyces cerevisiae, a conserved mRNA-binding protein, known as Cth2, modulates the metabolic response to iron deficiency. Cth2 is a tandem zinc-finger (TZF)-containing protein that co-transcriptionally binds to adenine/uracil-rich elements (ARE) present in the 3'-untranslated region of iron-related mRNAs to promote their turnover. The nuclear binding of Cth2 to mRNAs via its TZFs is indispensable for its export to the cytoplasm. Although Cth2 nucleocytoplasmic transport is essential for its regulatory function, little is known about the recruitment of the mRNA degradation machinery. Here, we investigate the sequential assembly of mRNA decay factors during Cth2 shuttling. By using an enzymatic in vivo proximity assay called M-track, we show that Cth2 associates to the RNA helicase Dhh1 and the deadenylase Pop2/Caf1 before binding to its target mRNAs. The recruitment of Dhh1 to Cth2 requires the integrity of the Ccr4-Pop2 deadenylase complex, whereas the interaction between Cth2 and Pop2 needs Ccr4 but not Dhh1. M-track assays also show that Cth2-binding to ARE-containing mRNAs is necessary for the interaction between Cth2 and the exonuclease Xrn1. The importance of these interactions is highlighted by the specific growth defect in iron-deficient conditions displayed by cells lacking Dhhl, Pop2, Ccr4 or Xrn1. These results exemplify the stepwise process of assembly of different mRNA decay factors onto an mRNA-binding protein during the mechanism of post-transcriptional regulation.