The Tob/BTG family is a group of antiproliferative proteins containing two highly homologous regions, Box A and Box B. These proteins all associate with CCR4-associated factor 1 (Caf1), which belongs to the ribonuclease D (RNase D) family of deadenylases and is a component of the CCR4-Not deadenylase complex. Here we determined the crystal structure of the complex of the N-terminal region of Tob and human Caf1 (hCaf1). Tob exhibited a novel fold, whereas hCaf1 most closely resembled the catalytic domain of yeast Pop2 and human poly(A)-specific ribonuclease. Interestingly, the association of hCaf1 was mediated by both Box A and Box B of Tob. Cell growth assays using both wild-type and mutant proteins revealed that deadenylase activity of Caf1 is not critical but complex formation is crucial to cell growth inhibition. Caf1 tethers Tob to the CCR4-Not deadenylase complex, and thereby Tob gathers several factors at its C-terminal region, such as poly(A)-binding proteins, to exert antiproliferative activity.