Chemical cross-linking and mass spectrometry are now widely used to analyze large-scale protein-protein interactions. The major challenge in cross-linking approaches is the complexity of the mass spectrometric data. New approaches are required that can identify cross-linked peptides with high-confidence and establish a user-friendly analysis protocol for the biomedical scientific community. Here, we introduce a novel cross-linker that can be selectively cleaved in the gas phase using two differential tandem mass-spectrometric fragmentation methods, such as collision-induced or electron transfer dissociation (CID and ETD). This technique produces two signature mass spectra of the same cross-linked peptide, thereby producing high confidence in identifying the sites of interaction. Further tandem mass spectrometry can also give additional confidence on the peptide sequences. We demonstrate a proof-of-concept for this method using standard peptides and proteins. Peptides and proteins were cross-linked and their fragmentation characteristics were analyzed using CID and ETD tandem mass spectrometry. Two sequential cleavages unambiguously identified cross-linked peptides. In addition, the labeling efficiency of the new cross-linker was evaluated in macrophage immune cells after stimulation with the microbial ligand lipopolysaccharide and subsequent pulldown experiments with biotin-avidin affinity chromatography. We believe this strategy will help advance insights into the structural biology and systems biology of cell signaling.