Tob protein, when overexpressed, suppresses growth of NIH3T3 cells, presumably by regulating expression of various growth-related genes. However, the molecular mechanisms underlying Tob-mediated regulation of gene expression have been obscure. To address this issue we established stable Tob-expressing cell lines and used a proteomics approach to identify Tob-interacting proteins. We found that Tob associates with the CCR4-NOT complex. The carboxyl-terminal half of Tob interacted with Cnot1, a core protein of the CCR4-NOT complex. We further showed that the deadenylase activity associated with the complex was suppressed in vitro by Tob. These results suggest that the antiproliferative activity of Tob is shown post-transcriptionally by controlling the stability of the target mRNAs in addition to its involvement in transcriptional regulation, reported previously.