The vitamin folate is required for methionine homeostasis in all organisms. In addition to its role in protein synthesis, methionine is the precursor to S-adenosyl-methionine (SAM), which is used in myriad cellular methylation reactions, including all histone methylation reactions. Here, we demonstrate that folate and methionine deficiency led to reduced methylation of lysine 4 of histone H3 (H3K4) in Saccharomyces cerevisiae. The effect of nutritional deficiency on H3K79 methylation was less pronounced, but was exacerbated in S. cerevisiae carrying a hypomorphic allele of Dot1, the enzyme responsible for H3K79 methylation. This result suggested a hierarchy of epigenetic modifications in terms of their susceptibility to nutritional limitations. Folate deficiency caused changes in gene transcription that mirrored the effect of complete loss of H3K4 methylation. Histone methylation was also found to respond to nutritional deficiency in the fission yeast Schizosaccharomyces pombe and in human cells in culture.