We describe optimized fragmentation schemes and data analysis strategies substantially enhancing the depth and accuracy in identifying protein cross-links using non-restricted whole proteome databases. These include a novel hybrid data acquisition strategy to sequence cross-links at both MS2 and MS3 level and a new algorithmic design XlinkX v2.0 for data analysis. As proof-of-concept we investigated proteome-wide protein interactions in E. coli and HeLa cell lysates, respectively, identifying 1,158 and 3,301 unique cross-links at ∼1% false discovery rate. These protein interaction repositories provide meaningful structural information on many endogenous macromolecular assemblies, as we showcase on several protein complexes involved in translation, protein folding and carbohydrate metabolism.