Cross-linking/Mass spectrometry (XLMS) is a consolidated technique for structural characterization of proteins and protein complexes. Despite its success, the cross-linking chemistry currently used is mostly based on N-hydroxysuccinimide (NHS) esters, which react primarily with lysine residues. One way to expand the current applicability of XLMS into several new areas is to increase the number of cross-links obtainable for a target protein. We introduce a multiplex chemistry (denoted XPlex) that targets Asp, Glu, Lys, and Ser residues. XPlex can generate significantly more cross-links with reactions occurring at lower temperatures and enables targeting proteins that are not possible with NHS ester-based cross-linkers. We demonstrate the effectiveness of our approach in model proteins as well as a target Lys-poor protein, SalBIII. Identification of XPlex spectra requires a search engine capable of simultaneously considering multiple cross-linkers on the same run; to achieve this, we updated the SIM-XL search algorithm with a search mode tailored toward XPlex. In summary, we present a complete chemistry/computational solution for significantly increasing the number of possible distance constraints by mass spectrometry experiments, and thus, we are convinced that XPlex poses as a real complementary approach for structural proteomics studies.