Tristetraprolin (TTP) is an RNA binding protein that controls the inflammatory response by limiting the expression of several proinflammatory cytokines. TTP post-transcriptionally represses gene expression by interacting with AU-rich elements (AREs) in 3′UTRs of target mRNAs and subsequently engenders their deadenylation and decay. TTP accomplishes these tasks, at least in part, by recruiting the multi subunit CCR4–NOT deadenylase complex to the mRNA. Here we identify an evolutionarily conserved C-terminal motif in human TTP that directly binds to a central domain of CNOT1, a core subunit of the CCR4–NOT complex. A high-resolution crystal structure of the TTP-CNOT1 complex was determined, providing the first structural insight into an ARE-binding protein bound to the CCR4–NOT complex. Mutations at the CNOT1-TTP interface impair TTP-mediated deadenylation, demonstrating the significance of this interaction in TTP-mediated gene silencing.