The application of non-cleavable cross-linkers to complex samples in XL-MS workflows is limited by the n² problem, a quadratic expansion of the search space with increasing database size. Here, a peptide-focused approach is proposed, for which cross-linking peptide candidates are identified in a parallel experiment by using a thiol-cleavable cross-linker with equal reactivity. Samples are reduced and alkylated, thereby releasing cross-linked peptides with a variable modification on the initially cross-linked residue. Modified peptides are identified by database search and concatenated to a peptide database, which is finally used for the analysis of the sample cross-linked with a non-cleavable cross-linker. This way, the search space is dramatically reduced leading to a higher sensitivity, because there is less chance for random hits to false positive sequences. The approach was benchmarked on cross-linked purified protein complexes (20 S Proteasome, yeast PolII, and TFIIH), and in vivo cross-linked bacteria (Bacillus subtilis, Bacillus cereus) by comparing it to the conventional approach of searching against the protein sequences.