Ten types of post-translational modifications (PTMs) known to be critical to diverse cellular functions have been described in core histone proteins. However, it remains unclear whether additional PTMs exist in histones, and if so, what roles these undiscovered signals play in epigenetic phenomena. Here, we report a systematic analysis of yeast histone PTMs by mass spectrometry in combination with protein sequence alignment using PTMap, a computer program we recently developed. We have identified, for the first time, multiple sites of lysine propionylation and butyrylation in yeast histones H2B, H3, and H4. We confirmed these modifications by Western blotting using modification-specific antibodies, MS/MS of synthetic peptides, and coelution of synthetic and in vivo-derived peptides from an HPLC column. The presence of multiple modification sites in several yeast histones suggests that these two PTMs are histone marks that are evolutionarily conserved among eukaryotes. In addition, we identified 14 novel mass shifts that do not match any known PTM, suggesting the presence of previously undescribed histone modifications. The chemical natures of these modifications remain to be determined. Our studies therefore expand current knowledge of the "histone code".