How epigenetic information is transmitted from generation to generation remains largely unknown. Deletion of the C. elegans Histone H3 lysine 4 dimethyl (H3K4me2) demethylase spr-5 leads to inherited accumulation of the euchromatic H3K4me2 mark and progressive decline in fertility. Here we identified multiple chromatin-modifying factors, including novel H3K4me1/me2 and H3K9me3 methyltransferases, an H3K9me3 demethylase and an H3K9me reader, which either suppress or accelerate the progressive transgenerational phenotypes of spr-5 mutant worms. Our findings uncover a network of chromatin regulators that control the trans-generational flow of epigenetic information, and suggest that the balance between euchromatic H3K4 and heterochromatic H3K9 methylation regulates trans-generational effects on fertility.