Less than half of all MS/MS spectra acquired in shotgun proteomics typically result in a confident peptide match. Here we present an ultra-tolerant Sequest database search that allowed peptide matching even with modifications of unknown masses up to ±500 Da. From an HEK293 cell proteome-wide dataset (9,513 proteins and 396,736 peptides), a ±500-Da search matched an additional 184,000 modified peptides. These were linked to both biological and chemical modifications representing 523 distinct mass bins including phosphorylation, glycosylation, and methylation. We attempted to localize all unknown modification masses to specific regions within a peptide, and known modifications were accurately assigned to the correct amino acids with frequencies often >90%. These data demonstrate that a large fraction of previously unassignable spectra are assignable to peptide sequences with modifications.