Protein-protein interactions play a vital role in nearly all cellular functions. Hence, understanding their interaction patterns and three-dimensional structural conformations can provide crucial insights about various biological processes and underlying molecular mechanisms for many disease phenotypes. Cross-linking mass spectrometry has the unique capability to detect protein-protein interactions at a large scale along with spatial constraints between interaction partners. However, the current cross-link search algorithms follow an MS2-centric approach and, as a result, suffer from a high rate of mis-identified cross-links (~15%). We address this urgent problem, by designing a novel MS3-centric approach for cross-link identification and implemented it as a search engine called MaXLinker. MaXLinker significantly outperforms the current state of the art search engine with up to 18-fold lower false positive rate. Additionally, MaXLinker results in up to 31% more cross-links, demonstrating its superior sensitivity and specificity. Moreover, we performed proteome-wide cross-linking mass spectrometry using K562 cells. Employing MaXLinker, we unveiled the most comprehensive set of 9,319 unique cross-links at 1% false discovery rate, comprising 8,051 intraprotein and 1,268 interprotein cross-links. Finally, we experimentally validated the quality of a large number of novel interactions identified in our study, providing a conclusive evidence for the robust performance of MaXLinker.