Polycomb Group (PcG) and Trithorax Group (TrxG) proteins are key epigenetic regulators of global transcription programs. Their antagonistic chromatin-modifying activities modulate the expression of many genes and affect many biological processes. Here we report that heterozygous mutations in two core subunits of Polycomb Repressive Complex 2 (PRC2), the histone H3 lysine 27 (H3K27)-specific methyltransferase E(Z) and its partner, the H3 binding protein ESC, increase longevity and reduce adult levels of trimethylated H3K27 (H3K27me3). Mutations in trithorax (trx), a well known antagonist of Polycomb silencing, elevate the H3K27me3 level of E(z) mutants and suppress their increased longevity. Like many long-lived mutants, E(z) and esc mutants exhibit increased resistance to oxidative stress and starvation, and these phenotypes are also suppressed by trx mutations. This suppression strongly suggests that both the longevity and stress resistance phenotypes of PRC2 mutants are specifically due to their reduced levels of H3K27me3 and the consequent perturbation of Polycomb silencing. Consistent with this, long-lived E(z) mutants exhibit derepression of Abd-B, a well-characterized direct target of Polycomb silencing, and Odc1, a putative direct target implicated in stress resistance. These findings establish a role for PRC2 and TRX in the modulation of organismal longevity and stress resistance and indicate that moderate perturbation of Polycomb silencing can increase longevity.