Campylobacter jejuni is the leading cause of acute bacterial gastroenteritis in the developed world and human infection is associated with consumption of contaminated poultry, in which the organism is considered an asymptomatic commensal species. Despite the prevalence of infection, the pathogenesis of C. jejuni remains poorly understood. The genome encodes ~1650 proteins, however greater than 50% remain functionally unknown and even less is known about their interactions, or the protein ‘interactome’. Analysis of protein interactions on a global scale is invaluable in developing an understanding of the interconnectivity of biochemical pathways, and ‘interactomics’ facilitated by large-scale, mass spectrometry (MS)-based proteomics has become the method-of-choice for identifying protein-protein interactions (PPIs). Cross-linking mass spectrometry (XL-MS) employs MS-cleavable chemical cross-linkers, such as disuccinimidyl sulfoxide (DSSO), which act to covalently link and stabilise interacting proteins, and allow their unambiguous identification by MS/MS. As a result, XL-MS can be used to predict the function of unknown proteins, validate protein subcellular localisations, refine protein structures, and define significant interaction networks. A novel and optimised approach for XL-MS using DSSO, off-line peptide size exclusion chromatography and a hybrid MS2-MS3 fragmentation strategy was developed and employed to globally define PPIs in C. jejuni. This enabled the first non-binary and comprehensive analysis of the interactome of this organism. A total of 745 proteins were identified to partake in 1,133 unique and significant PPIs governed by 3,316 unique Lys-Lys residue contacts. Our XL-MS approach successfully covered 46% of the predicted proteome of C. jejuni and 57.3% of the proteome as previously identified by ‘bottom-up’ proteomics. Additionally, multiple proteases and enrichment strategies were compared and this allowed for increased depth and coverage of the proteome, as well as the identification of less abundant and harder to detect PPIs and cross-links, particularly membrane proteins. Interrogation of the XL-MS dataset returned known interactions and a large subset of novel interactions, and validated XL-MS as an effective approach to identify, analyse and characterise in vivo PPIs and protein complexes in C. jejuni.