Identification of post-translational modifications (PTMs) is important to understand biological functions of proteins. Tandem mass spectrometry (MS/MS) is a useful tool for identifying PTMs. However, most existing search tools are restricted to take only a few types of PTMs as input. We describe here a new algorithm, called MODi (pronounced as ‘mod eye’), which rapidly searches for all known types of PTMs at once, without limiting a multitude of modified sites in a peptide. MODi introduces a notion of a tag chain, a combination structure made from multiple sequence tags, which effectively localizes modified regions within a spectrum and overcomes de novo sequencing errors common in tag-based approaches. MODi showed its performance competence by identifying various types of PTMs in analysis of PTM-rich proteins such as GAPDH (Glyceraldehyde-3-phosphate dehydrogenase) and lens protein. We demonstrated that MODi innovatively manages the computational complexity for identifying multiple PTMs in a peptide, which may exist in a greater variety than usually expected. In addition, it is suggested that MODi has a great potential for discovering novel modifications.