Polycomb complexes regulate cell type-specific gene expression programs through heritable silencing of target genes. Trimethylation of histone H3 lysine 27 (H3K27me3) is essential for this process. Perturbation of H3K36 is thought to interfere with H3K27me3. We show that mutants of Drosophila replication-dependent (H3.2K36R) or replication-independent (H3.3K36R) histone H3 genes generally maintain Polycomb silencing and reach later stages of development. In contrast, combined (H3.3K36RH3.2K36R) mutants display widespread Hox gene misexpression and fail to develop past the first larval stage. Chromatin profiling revealed that the H3.2K36R mutation disrupts H3K27me3 levels broadly throughout silenced domains, whereas these regions are mostly unaffected in H3.3K36R animals. Analysis of H3.3 distributions showed that this histone is enriched at presumptive Polycomb response elements located outside of silenced domains but relatively depleted from those inside. We conclude that H3.2 and H3.3 K36 residues collaborate to repress Hox genes using different mechanisms.