Heterochromatin assembly in budding yeast requires the SIR complex, which contains the NAD-dependent deacetylase Sir2 and the Sir3 and Sir4 proteins. Sir3 binds to nucleosomes containing deacetylated histone H4 lysine 16 (H4K16) and, with Sir4, promotes spreading of Sir2 and deacetylation along the chromatin fiber. Combined action of histone modifying and binding activities is a conserved hallmark of heterochromatin, but the relative contribution of each activity to silencing has remained unclear. Here, we reconstitute SIR-chromatin complexes using purified components and show that the SIR complex efficiently deacetylates chromatin templates and promotes the assembly of altered structures that silence Gal4-VP16-activated transcription. Silencing requires all three Sir proteins, even with fully deacetylated chromatin, and involves the specific association of Sir3 with deacetylated H4K16. These results define a minimal set of components that mediate heterochromatic gene silencing and demonstrate distinct contributions for histone deacetylation and nucleosome binding in the silencing mechanism.