Shotgun proteomics has been widely used to identify histone marks. Conventional database search methods rely on the “target-decoy” strategy to calculate the false discovery rate (FDR) and distinguish true peptide-spectrum matches (PSMs) from false ones. This strategy has a caveat of inaccurate FDR caused by the small data size of histone marks. To address this challenge, we developed a tailored database search strategy, named “Comprehensive Histone Mark Analysis (CHiMA).” Instead of target-decoy–based FDR, this method uses “50% matched fragment ions” as the key criterion to identify high-confidence PSMs. CHiMA identified twice as many histone modification sites as the conventional method in benchmark datasets. Reanalysis of our previous proteomics data using CHiMA led to the identification of 113 new histone marks for four types of lysine acylations, almost doubling the number of previously reported marks. This tool not only offers a valuable approach for identifying histone modifications but also greatly expands the repertoire of histone marks.