Profound epigenetic differences exist between genomes derived from male and female gametes; however, the nature of these changes remains largely unknown. We undertook a systematic investigation of chromatin reorganization during gametogenesis, using the model eukaryote Saccharomyces cerevisiae to examine sporulation, which has strong similarities with higher eukaryotic spermatogenesis. We established a mutational screen of histones H3 and H4 to uncover substitutions that reduce sporulation efficiency. We discovered two patches of residues—one on H3 and a second on H4—that are crucial for sporulation but not critical for mitotic growth, and likely comprise interactive nucleosomal surfaces. Furthermore, we identified novel histone post-translational modifications that mark the chromatin reorganization process during sporulation. First, phosphorylation of H3T11 appears to be a key modification during meiosis, and requires the meiotic-specific kinase Mek1. Second, H4 undergoes amino tail acetylation at Lys 5, Lys 8, and Lys 12, and these are synergistically important for post-meiotic chromatin compaction, occurring subsequent to the post-meiotic transient peak in phosphorylation at H4S1, and crucial for recruitment of Bdf1, a bromodomain protein, to chromatin in mature spores. Strikingly, the presence and temporal succession of the new H3 and H4 modifications are detected during mouse spermatogenesis, indicating that they are conserved through evolution. Thus, our results show that investigation of gametogenesis in yeast provides novel insights into chromatin dynamics, which are potentially relevant to epigenetic modulation of the mammalian process.