Updated publication reference for PubMed record(s): 30936560. Thousands of protein post-translational modifications (PTMs) dynamically impact nearly all cellular functions. Although mass spectrometry is suited to PTM identification, it has historically been biased towards a few with established enrichment procedures. To measure all possible PTMs across diverse proteomes, software must overcome two fundamental challenges: intractably large search spaces and difficulty distinguishing correct from incorrect identifications. Here, we describe TagGraph, software that overcomes both challenges with a string-based search method that is orders of magnitude faster than current approaches, and a probabilistic validation model optimized for PTM assignments. When applied to a human proteome map, TagGraph triples confident identifications while revealing thousands of modification types spanning nearly one million sites across the proteome. We show new contexts for highly abundant yet understudied PTMs such as proline hydroxylation. TagGraph expands our ability to survey the full proteomic landscape of PTMs, shedding new light on their tissue-specific functions.