The assembly of heterochromatin in fission yeast and metazoans requires histone H3-lysine 9 (-K9) methylation by the conserved Clr4/Suv39h methyltransferase. In fission yeast, H3-K9 methylation requires components of the RNAi machinery and is initiated by the RNA-Induced Transcriptional Silencing (RITS) complex. Here we report the purification of a novel complex that associates with the Clr4 methyltransferase, termed the CLRC (CLr4-Rik1-Cul4) complex. By affinity purification of the Clr4-associated protein Rik1, we show that, in addition to Clr4, Rik1 is associated with the fission yeast E3 ubiquitin ligase Cullin4 (Cul4, encoded by cul4(+)), the ubiquitin-like protein, Ned8, and two previously uncharacterized proteins, designated Cmc1 and Cmc2. In addition, the complex contains substochiometric amounts of histones H2B and H4, and the 14-3-3 protein, Rad24. Deletion of cul4(+), cmc1(+), cmc2(+) and rad24(+) results in a complete loss of silencing of a ura4(+) reporter gene inserted within centromeric DNA repeats or the silent mating type locus. Each of the above deletions also results in accumulation of noncoding RNAs transcribed from centromeric repeats and telomeric DNA regions, and a corresponding loss of small RNAs that are homologous to centromeric repeats, suggesting a defect in the processing of noncoding RNA to small RNA. Based on these results, we propose that the components of the Clr4-Rik1-Cul4 complex act concertedly at an early step in heterochromatin formation.