Most protein complexes are inaccessible to high resolution structural analysis. We report the results of a combined approach of cross-linking, mass spectrometry, and bioinformatics to two human complexes containing large coiled-coil segments, the NDEL1 homodimer and the NDC80 heterotetramer. An important limitation of the cross-linking approach, so far, was the identification of cross-linked peptides from fragmentation spectra. Our novel approach overcomes the data analysis bottleneck of cross-linking and mass spectrometry. We constructed a purpose-built database to match spectra with cross-linked peptides, define a score that expresses the quality of our identification, and estimate false positive rates. We show that our analysis sheds light on critical structural parameters such as the directionality of the homodimeric coiled coil of NDEL1, the register of the heterodimeric coiled coils of the NDC80 complex, and the organization of a tetramerization region in the NDC80 complex. Our approach is especially useful to address complexes that are difficult in addressing by standard structural methods.