Heterochromatin is essential for chromosome segregation, gene silencing and genome integrity. The fission yeast Schizosaccharomyces pombe contains heterochromatin at centromeres, subtelomeres, and mating type genes, as well as at small islands of meiotic genes dispersed across the genome. This heterochromatin is generated by partially redundant mechanisms, including the production of small interfering RNAs (siRNAs) that are incorporated into the RITS protein complex (RNAi-Induced Transcriptional Silencing). The assembly of heterochromatin islands requires the function of the RNA-binding protein Mmi1, which recruits RITS to its mRNA targets and to heterochromatin islands. In addition, Mmi1 directs its targets to an exosome-dependent RNA elimination pathway. Ccr4-Not is a conserved multiprotein complex that regulates gene expression at multiple levels, including RNA degradation and translation. We show here that Ccr4-Not is recruited by Mmi1 to its RNA targets. Surprisingly, Ccr4 and Caf1 (the mRNA deadenylase catalytic subunits of the Ccr4-Not complex) are not necessary for the degradation or translation of Mmi1 RNA targets, but are essential for heterochromatin integrity at Mmi1-dependent islands and, independently of Mmi1, at subtelomeric regions. Both roles require the deadenylase activity of Ccr4 and the Mot2/Not4 protein, a ubiquitin ligase that is also part of the complex. Genetic evidence shows that Ccr4-mediated silencing is essential for normal cell growth, indicating that this novel regulation is physiologically relevant. Moreover, Ccr4 interacts with components of the RITS complex in a Mmi1-independent manner. Taken together, our results demonstrate that the Ccr4-Not complex is required for heterochromatin integrity in both Mmi1-dependent and Mmi1-independent pathways.