Protein-protein interactions within complexes and networks are often dynamic and their elucidation remains a challenging task. Here, we show on the example of the proteolytic ClpXP complex the power of combined chemical cross-linking and mass-spectrometry to capture transient binding interactions within ClpP and ClpX as well as across the enigmatic ClpX hexamer – ClpP heptamer interface. Our data suggests that a few hot spot lysine residues located in signature loops in ClpX mediate the ClpX-ClpP interaction. This study further confirms that Listeria monocytogenes ClpX solely interacts with the heterooligomeric ClpP1/2 complex via the ClpP2 apical site. Moreover, the cellular interaction network of human and bacterial proteases was elucidated via in situ chemical cross-linking followed by an antibody-based pull-down against ClpP from genetically unmodified cells. A subsequent gel-free, quantitative mass spectrometric analysis demonstrated an up to 3-fold higher coverage compared to conventional co-immunoprecipitation without cross-linker revealing unprecedented insight into intracellular ClpXP networks.