The mass spectrometric identification of chemically cross-linked peptides (CXMS) specifies spatial restraints of protein complexes; these values complement data obtained from common structure-determination techniques. Generic methods for determining false discovery rates of cross-linked peptide assignments are currently lacking, thus making data sets from CXMS studies inherently incomparable. Here we describe an automated target-decoy strategy and the software tool xProphet, which solve this problem for large multicomponent protein complexes.