Combinatorial post-translational modifications (PTMs), such as those forming the so-called “histone code”, have been linked to cell differentiation, embryonic development, cellular reprogramming, aging, cancers, neurodegenerative disorders, etc. Nevertheless, a reliable mass spectral analysis of the combinatorial isomers represents a considerable challenge. The difficulty stems from the incompleteness of information that could be generated by the standard MS to differentiate cofragmented isomeric sequences in their naturally occurring mixtures based on the fragment mass-to-charge ratio and relative abundance information only. Here we show that fragment–fragment correlations revealed by two-dimensional partial covariance mass spectrometry (2D-PC-MS) allow one to solve the combinatorial PTM puzzles that cannot be tackled by the standard MS as a matter of principle. We introduce 2D-PC-MS marker ion correlation approach and demonstrate experimentally that it can provide the missing information enabling identification of cofragmentated combinatorially modified isomers. Our in silico study shows that the marker ion correlations can be used to unambiguously identify 5 times more cofragmented combinatorially acetylated tryptic peptides and 3 times more combinatorially modified Glu-C peptides of human histones than is possible using standard MS methods.