Mass spectrometry (MS) is a powerful analytical method for the identification and quantification of co-existing post-translational modifications (PTMs) in histone proteins. One of the most important challenges in current chromatin biology is to characterize the relationships between co-existing histone marks, the order and hierarchy of their deposition and their distinct biological functions. We developed a database CrossTalkDB to organize observed and reported co-existing histone marks as revealed by MS experiments of histone proteins and their derived peptides. Statistical assessment revealed sample-specific patterns for the co-frequency of histone PTMs. We implemented a new method to identify positive and negative interplay between pairs of methylation and acetylation marks in proteins. Many of the detected features were conserved between different cell types, or exist across species, thereby revealing general rules for crosstalk between histone marks. The observed features are in accordance with previously reported examples of crosstalk. We observed novel types of interplay (1) among acetylated residues, revealing positive crosstalk between nearby acetylated sites but negative crosstalk for distant ones, and (2) for discrete methylation states at K9, K27 and K36 of histone H3, suggesting a more differentiated functional role of methylation beyond the general expectation of enhanced activity at higher methylation states.