Cross-linking mass spectrometry (XL-MS) has received considerable interest, owing to its potential to investigate protein-protein interactions (PPIs) in an unbiased fashion in complex protein mixtures. Recent developments have enabled the detection of thousands of PPIs from a single experiment. A unique strength of XL-MS, in comparison with other methods for determining PPIs, is that it provides direct spatial information for the detected interactions. This is accomplished by the use of bifunctional cross-linking molecules that link two amino acids in close proximity with a covalent bond. Upon proteolytic digestion, this results in two newly linked peptides, which are identifiable by MS. XL-MS has received the required boost to tackle more-complex samples with recent advances in cross-linking chemistry with MS-cleavable or reporter-based cross-linkers and faster, more sensitive and more versatile MS platforms. This protocol provides a detailed description of our optimized conditions for a full-proteome native protein preparation followed by cross-linking using the gas-phase cleavable cross-linking reagent disuccinimidyl sulfoxide (DSSO). Following cross-linking, we demonstrate extensive sample fractionation and substantially simplified data analysis with XlinkX in Proteome Discoverer, as well as subsequent protein structure investigations with DisVis and HADDOCK. This protocol produces data of high confidence and can be performed within ~10 d, including structural investigations.