For the analysis of homogenous post-translational modification such as protein phosphorylation, acetylation, setting a variable modification on the specific residue(s) is applied to identify the modified peptides for database searching. However, this approach is often not applicable to identify intact mucin-type O-glycopeptides due to the high microheterogeneity of the glycosylation. Because there is virtually no carbohydrate-related tag on the peptide fragments after the O-glycopeptides are dissociated in HCD, we find it is unnecessary to set the variable mass tags on the Ser/Thr residues to identify the peptide sequences. In this study, we present a novel approach, termed as O-Search, for the interpretation of O-glycopeptides’ HCD spectra. Instead of setting the variable mass tags on the Ser/Thr residues, we set variable mass tags on the peptide level. The precursor mass of the MS/MS spectrum was deducted by every possible summed masses of O-glycan combinations on at most three S/T residues. All the spectra with these new precursor masses were searched against the protein sequence database without setting variable glycan modifications. It was found that this method had much decreased search space and had excellent sensitivity in the identification of O-glycopeptides. Compared with the conventional searching approach, O-Search yielded 96%, 86% and 79% improvement in glycopeptide spectra matching, glycopeptide identification and the peptide sequence identification, respectively. It was demonstrated that O-Search enabled the consideration of more glycan structures and was fitted to analyze microheterogeneity of O-glycosylation.