Epigenetically regulated heterochromatin domains govern essential cellular activities. A key feature of heterochromatin domains is the presence of hypoacetylated nucleosomes, which are methylated on lysine 9 of histone H3 (H3K9me). Here, we investigate the requirements for establishment, spreading and maintenance of heterochromatin using fission yeast centromeres as a paradigm. We show that establishment of heterochromatin on centromeric repeats is initiated at modular ‘nucleation sites’ by RNA interference (RNAi), ensuring the mitotic stability of centromere-bearing minichromosomes. We demonstrate that the histone deacetylases Sir2 and Clr3 and the chromodomain protein Swi6HP1 are required for H3K9me spreading from nucleation sites, thus allowing formation of extended heterochromatin domains. We discovered that RNAi and Sir2 along with Swi6HP1 operate in two independent pathways to maintain heterochromatin. Finally, we demonstrate that tethering of Sir2 is pivotal to the maintenance of heterochromatin at an ectopic locus in the absence of RNAi. These analyses reveal that Sir2, together with RNAi, are sufficient to ensure heterochromatin integrity and provide evidence for sequential establishment, spreading and maintenance steps in the assembly of centromeric heterochromatin.