For structural studies of proteins and their complexes, chemical cross-linking combined with mass spectrometry presents a promising strategy to obtain structural data of protein interfaces from low quantities of proteins within a short time. We explore the use of isotope-labeled cross-linkers in combination with Fourier transform ion cyclotron resonance (FTICR) mass spectrometry for a more efficient identification of cross-linker containing species. For our studies, we chose the calcium-independent complex between calmodulin and a 25-amino acid peptide from the C-terminal region of adenylyl cyclase 8 containing an "IQ-like motif." Cross-linking reactions between calmodulin and the peptide were performed in the absence of calcium using the amine-reactive, isotope-labeled (d0 and d4) cross-linkers BS3 (bis[sulfosuccinimidyl]suberate) and BS2G (bis[sulfosuccinimidyl]glutarate). Tryptic in-gel digestion of excised gel bands from covalently cross-linked complexes resulted in complicated peptide mixtures, which were analyzed by nano-HPLC/nano-ESI-FTICR mass spectrometry. In cases where more than one reactive functional group, e.g., amine groups of lysine residues, is present in a sequence stretch, MS/MS analysis is a prerequisite for unambiguously identifying the modified residues. MS/MS experiments revealed two lysine residues in the central alpha-helix of calmodulin as well as three lysine residues both in the C-terminal and N-terminal lobes of calmodulin to be cross-linked with one single lysine residue of the adenylyl cyclase 8 peptide. Further cross-linking studies will have to be conducted to propose a structural model for the calmodulin/peptide complex, which is formed in the absence of calcium. The combination of using isotope-labeled cross-linkers, determining the accurate mass of intact cross-linked products, and verifying the amino acid sequences of cross-linked species by MS/MS presents a convenient approach that offers the perspective to obtain structural data of protein assemblies within a few days.