The post-genome era has been driven by global technologies such as transcriptomics and proteomics that have enabled comparative analyses of cells, tissues and organisms under ‘control’ and ‘test’ conditions. This research however, while hugely significant, has generally ignored the dimensionality of protein biochemistry; while concentrating on the relative abundance of transcripts and proteins, the knowledge that proteins largely convey functions by forming transient or covalent interactions, such as protein complexes, has been mostly neglected. C. jejuni is the leading cause of bacterial gastroenteritis in the developed world. The organism maintains an unusual biochemistry underpinned by a small genome (~1620 genes) that encodes a large repertoire of functionally unknown proteins. Given the atypical nature of C. jejuni virulence, we utilised high resolution mass spectrometry (MS) and cross-linking MS (XL-MS) to define the interactome in this organism. We further developed a tandem mass tag (TMT)-based quantitative XL-MS (qXL-MS) strategy that was employed to demonstrate the dynamic nature of interactions under altered environmental conditions, particularly over a short time-frame (‘shock’) where vast protein abundance changes are limited. Specifically, cold (at 4°C) and heat shock (at 45°C) were assessed via changes to biomolecular interactions. Altered interactions involved two-component regulatory systems, chaperones, transcription / translation, and flagellar motility. In addition, membrane protein interactions favoured changes that protect membrane fluidity and integrity. Utilising qXL-MS to investigate changes in protein interactions, conformations, and stability provided an additional layer of complexity to the temperature stress response unable to be captured with proteomics and transcriptomics approaches alone.