Chemical cross-linking coupled with mass spectrometry plays an important role in unravelling protein interactions, especially weak and transient interactions. Moreover, cross-linking complements several structure determination approaches such as cryo-EM. Although several computational approaches are available for the annotation of spectra obtained from cross-linked peptides, there remains room for improvement. Here, we present Xilmass, a novel algorithm to identify cross-linked peptides that introduces two new concepts: (i) the cross-linked peptides are represented in a novel way in the search database that explicitly encodes cross-linking sites and (ii) the scoring function from the Andromeda algorithm was adapted to score against a theoretical MS spectrum that contains the peaks from all the possible fragment ions of a cross-linked peptide pair. The performance of Xilmass was subsequently evaluated against the recently published Kojak and the popular pLink algorithms on a data set that contains calmodulin-plectin.