Saccharomyces cerevisiae has the most comprehensively characterized protein-protein interaction network, or interactome, of any eukaryote. This has predominantly been generated through multiple, systematic studies of protein-protein interactions by two-hybrid techniques and of affinity-purified protein complexes. A pressing question is to understand how large-scale cross-linking mass spectrometry (XL-MS) can confirm and extend this interactome. Here, intact yeast nuclei were subject to cross-linking with disuccinimidyl sulfoxide (DSSO) and analyzed using hybrid MS2-MS3 methods. XlinkX identified a total of 2,052 unique residue pair cross-links at 1% FDR. Intraprotein cross-links were found to provide extensive structural constraint data, with almost all intralinks that mapped to known structures and slightly fewer of those mapping to homology models being within 30 Å. Intralinks provided structural information for a further 366 proteins. A method for optimizing interprotein cross-link score cut-offs was developed, through use of extensive known yeast interactions. Its application led to a high confidence, yeast nuclear interactome. Strikingly, almost half of the interactions were not previously detected by two-hybrid or AP-MS techniques. Multiple lines of evidence existed for many such interactions, whether through literature or ortholog interaction data, through multiple unique interlinks between proteins, and/or through replicates. We conclude that XL-MS is a powerful means to measure interactions, that complements two-hybrid and affinity-purification techniques.