Fission yeast heterochromatin is formed at centromeres, telomeres, and in the mating-type region where it mediates the transcriptional silencing of the mat2-P and mat3-M donor loci and the directionality of mating-type switching. We conducted a genetic screen for directionality mutants. This screen revealed the essential role of two previously uncharacterized factors, Clr7 and Clr8, in heterochromatin formation. Clr7 and Clr8 are required for localization of the Swi6 chromodomain protein and for histone H3 lysine 9 methylation, thereby influencing not only mating-type switching but also transcriptional silencing in all previously characterized heterochromatic regions, chromosome segregation, and meiotic recombination in the mating-type region. We present evidence for physical interactions between Clr7 and the mating-type region and between Clr7 and the S. pombe cullin Pcu4, indicating that a complex containing these proteins mediates an early step in heterochromatin formation and implying a role for ubiquitination at this early stage prior to the action of the Clr4 histone methyl-transferase. Like Clr7 and Clr8, Pcu4 is required for histone H3 lysine 9 methylation, and bidirectional centromeric transcripts that are normally processed into siRNA by the RNAi machinery in wild-type cells are easily detected in cells lacking Clr7, Clr8, or Pcu4. Another physical interaction, between the nucleoporin Nup189 and Clr8, suggests that Clr8 might be involved in tethering heterochromatic regions to the nuclear envelope by association with the nuclear-pore complex.