Dysregulation of chromatin methylation is associated with defects in cellular differentiation as well as a variety of cancers. How cells regulate the opposing activities of histone methyltransferase and demethylase enzymes to set the methylation status of the epigenome for proper control of gene expression and metabolism remains poorly understood. Here, we show that loss of methylation of the major phosphatase PP2A in response to methionine starvation activates the demethylation of histones through hyperphosphorylation of specific demethylase enzymes. In parallel, this regulatory mechanism enables cells to preserve SAM by increasing SAH to limit SAM consumption by methyltransferase enzymes. Mutants lacking the PP2A methyltransferase or the effector H3K36 demethylase Rph1 exhibit elevated SAM levels and are dependent on cysteine due to reduced capacity to sink the methyl groups of SAM. Therefore, PP2A directs the methylation status of histones by regulating the phosphorylation status of histone demethylase enzymes in response to SAM levels.