Recent studies have revealed diverse amino acid, post-translational and non-canonical modifications of proteins in diverse organisms and tissues. However, their unbiased detection and analysis remain hindered by technical limitations. Here, we present a spectral alignment method for the identification of protein modifications from high-resolution tandem peptide mass spectrometry. Termed SAMPEI for Spectral Alignment-based Modified PEptide Identification, this open-source algorithm is designed for the discovery of functional protein and peptide signaling modifications, without prior knowledge of their identities. Using synthetic standards and controlled chemical labeling experiments, we demonstrate specificity and sensitivity of SAMPEI for the discovery of protein modifications in complex cellular extracts. We then apply SAMPEI to mapping chemical protein modifications in differentiating mouse macrophage proteome. SAMPEI revealed diverse post-translational protein modifications, including distinct forms of cysteine itaconatylation which we experimentally validated. SAMPEI’s robust parameterization and versatility are expected to facilitate the discovery of biological modifications of diverse macromolecules. SAMPEI is implemented as a Python package and is available open-source from BioConda and GitHub (https://github.com/FenyoLab/SAMPEI). The dataset is divided in 3 set of files: 1. Agnostic_discovery_benchmarking.zip file contains analyses performed to establish relative sensitivity and specificity of agnostic PTM discovery (Figure 2, Figure S3). 2. Chemoproteomics_of_LPS_stimulated_macrophages.zip file contains RAW264.7 cell proteomics identification results from X!tandem and SAMPEI (Figure 3, Figures S4-S7). 3. Itaconate_adducts_validation.zip file contains analysis to confirm cystein adducts produced by itaconic acid (Figure 5, Figures S8-S12).