We describe distinct patterns of histone methylation during human cell cycle progression. Histone H4 methyltransferase activity was found to be cell cycle-regulated, consistent with increased H4 Lys 20 methylation at mitosis. This increase closely followed the cell cycle-regulated expression of the H4 Lys 20 methyltransferase, PR-Set7. Localization of PR-Set7 to mitotic chromosomes and subsequent increase in H4 Lys 20 methylation were inversely correlated to transient H4 Lys 16 acetylation in early S-phase. These data suggest that H4 Lys 20 methylation by PR-Set7 during mitosis acts to antagonize H4 Lys 16 acetylation and to establish a mechanism by which this mark is epigenetically transmitted.