In mammalian cells, mRNA decay begins with deadenylation, which involves two consecutive phases mediated by the PAN2-PAN3 and the CCR4-CAF1 complexes, respectively. The regulation of the critical deadenylation step and its relationship with RNA-processing bodies (P-bodies), which are thought to be a site where poly(A)-shortened mRNAs get degraded, are poorly understood. Using the Tet-Off transcriptional pulsing approach to investigate mRNA decay in mouse NIH 3T3 fibroblasts, we found that TOB, an antiproliferative transcription factor, enhances mRNA deadenylation in vivo. Results from glutathione S-transferase pull-down and coimmunoprecipitation experiments indicate that TOB can simultaneously interact with the poly(A) nuclease complex CCR4-CAF1 and the cytoplasmic poly(A)-binding protein, PABPC1. Combining these findings with those from mutagenesis studies, we further identified the protein motifs on TOB and PABPC1 that are necessary for their interaction and found that interaction with PABPC1 is necessary for TOB's deadenylation-enhancing effect. Moreover, our immunofluorescence microscopy results revealed that TOB colocalizes with P-bodies, suggesting a role of TOB in linking deadenylation to the P-bodies. Our findings reveal a new mechanism by which the fate of mammalian mRNA is modulated at the deadenylation step by a protein that recruits poly(A) nuclease(s) to the 3' poly(A) tail-PABP complex.