A plant's experience of abiotic or biotic stress can lead to stress memory in order to react faster and more efficiently to subsequent stresses. Molecularly, the memory of a stress can rely on stable inheritance through mitotic and meiotic cell divisions, thus epigenetic inheritance. The key epigenetic regulators are DNA cytosine methyltransferases and the Polycomb group (PcG) and Trithorax group (TrxG) proteins, which control numerous developmental processes. PcG and TrxG proteins act antagonistically on stable gene repression through mediating trimethylation of histone H3 lysine 27 (H3K27me3) and H3K4me3, respectively, and target thousands of genes in plants, including many genes responsive to stress. The role of PcG/TrxG proteins in regulating stress responses and memory, however, is just emerging. While it is well investigated that stress can induce changes of histone modifications at genes regulated by stress, it is largely unclear whether these changes are mitotically and/or meiotically heritable, hence confer somatic and/or transgenerational stress memory. As the literature on the role of DNA methylation in regulating stress responses has recently been extensively summarized, we focus this review on the current knowledge on the role of PcG and TrxG in stress responses and memory.