Protein modification by small ubiquitin-like modifier (SUMO) modulates the activities of numerous proteins involved in different cellular functions such as gene transcription, cell cycle, and DNA repair. Comprehensive identification of SUMOylated sites is a prerequisite to determine how SUMOylation regulates protein function. However, mapping SUMOylated Lys residues by mass spectrometry (MS) is challenging because of the dynamic nature of this modification, the existence of three functionally distinct human SUMO paralogs, and the large SUMO chain remnant that remains attached to tryptic peptides. To overcome these problems, we created HEK293 cell lines that stably express functional SUMO paralogs with an N-terminal His6-tag and an Arg residue near the C terminus that leave a short five amino acid SUMO remnant upon tryptic digestion. We determined the fragmentation patterns of our short SUMO remnant peptides by collisional activation and electron transfer dissociation using synthetic peptide libraries. Activation using higher energy collisional dissociation on the LTQ-Orbitrap Elite identified SUMO paralog-specific fragment ions and neutral losses of the SUMO remnant with high mass accuracy (< 5 ppm). We exploited these features to detect SUMO modified tryptic peptides in complex cell extracts by correlating mass measurements of precursor and fragment ions using a data independent acquisition method. We also generated bioinformatics tools to retrieve MS/MS spectra containing characteristic fragment ions to the identification of SUMOylated peptide by conventional Mascot database searches. In HEK293 cell extracts, this MS approach uncovered low abundance SUMOylated peptides and 37 SUMO3-modified Lys residues in target proteins, most of which were previously unknown. Interestingly, we identified mixed SUMO-ubiquitin chains with ubiquitylated SUMO proteins (K20 and K32) and SUMOylated ubiquitin (K63), suggesting a complex crosstalk between these two modifications.