Many cellular functions necessitate structural assemblies of two or more associated proteins. The structural characterization of protein complexes using standard methods, such as X-ray crystallography, is challenging. Herein, we describe an orthogonal approach using hydrogen-deuterium-exchange mass spectrometry (HDXMS), cross-linking mass spectrometry (CXMS), and disulfide trapping to map interactions within protein complexes. HDXMS measures changes in solvent accessibility and hydrogen bonding upon complex formation; a decrease in HDX rate could account for newly formed intermolecular or intramolecular interactions. To distinguish between inter- and intramolecular interactions, we use a CXMS method to determine the position of direct interface regions by trapping intermolecular residues in close proximity to various cross-linkers (e.g., disuccinimidyl adipate (DSA)) of different lengths and reactive groups. Both MS-based experiments are performed on high-resolution mass spectrometers (e.g., an Orbitrap Elite hybrid mass spectrometer). The physiological relevance of the interactions identified through HDXMS and CXMS is investigated by transiently co-expressing cysteine mutant pairs, one mutant on each protein at the discovered interfaces, in an appropriate cell line, such as HEK293. Disulfide-trapped protein complexes are formed within cells spontaneously or are facilitated by addition of oxidation reagents such as H2O2 or diamide. Western blotting analysis, in the presence and absence of reducing reagents, is used to determine whether the disulfide bonds are formed in the proposed complex interface in physiologically relevant milieus. The procedure described here requires 1-2 months. We demonstrate this approach using the β2-adrenergic receptor-β-arrestin1 complex as the model system.