Heterochromatin silencing is pivotal for genome stability in eukaryotes. In Arabidopsis, a plant-specific mechanism called RNA–directed DNA methylation (RdDM) is involved in heterochromatin silencing. Histone deacetylase HDA6 has been identified as a component of such machineries; however, its endogenous targets and the silencing mechanisms have not been analyzed globally. In this study, we investigated the silencing mechanism mediated by HDA6. Genome-wide transcript profiling revealed that the loci silenced by HDA6 carried sequences corresponding to the RDR2-dependent 24-nt siRNAs, however their transcript levels were mostly unaffected in the rdr2 mutant. Strikingly, we observed significant overlap of genes silenced by HDA6 to those by the CG DNA methyltransferase MET1. Furthermore, regardless of dependence on RdDM pathway, HDA6 deficiency resulted in loss of heterochromatic epigenetic marks and aberrant enrichment for euchromatic marks at HDA6 direct targets, along with ectopic expression of these loci. Acetylation levels increased significantly in the hda6 mutant at all of the lysine residues in the H3 and H4 N-tails, except H4K16. Interestingly, we observed two different CG methylation statuses in the hda6 mutant. CG methylation was sustained in the hda6 mutant at some HDA6 target loci that were surrounded by flanking DNA–methylated regions. In contrast, complete loss of CG methylation occurred in the hda6 mutant at the HDA6 target loci that were isolated from flanking DNA methylation. Regardless of CG methylation status, CHG and CHH methylation were lost and transcriptional derepression occurred in the hda6 mutant. Furthermore, we show that HDA6 binds only to its target loci, not the flanking methylated DNA, indicating the profound target specificity of HDA6. We propose that HDA6 regulates locus-directed heterochromatin silencing in cooperation with MET1, possibly recruiting MET1 to specific loci, thus forming the foundation of silent chromatin structure for subsequent non-CG methylation. Eukaryotes are defended from potentially harmful DNA elements, such as transposons, by forming inactive genomic structure. Chromatin, which consists of DNA and histone proteins, is densely packed in the silent structure, and chromatin chemical modifications such as DNA methylation and histone modifications are known to be essential for this packing. In plants, small RNA molecules have been thought to trigger DNA methylation and resulting silent chromatin formation. We revealed that elimination of specific histone modifications concomitant with DNA methylation is pivotal for the silent chromatin. Furthermore, the histone deacetylase was shown to have more profound target specificity than the DNA methyltransferase and is required for locus-directed DNA methylation, implying the involvement of the histone deacetylase for targeting the DNA methyltransferase to specific places on the genome. These proteins and their functions for gene silencing are evolutionarily conserved in higher eukaryotes, and several proteins involved in small RNA production are plant-specific. Thus, we present a hypothesis that the plant genome may build the protecting foundation by the conserved genome surveillance in eukaryotes, and the reinforcing machinery involving small RNAs could be evolutionarily added to the plant heterochromatin silencing system.