Protein interactions regulate the systems-level behavior of cells; thus, deciphering the structure and dynamics of protein interaction networks in their cellular context is a central goal in biology. We have performed a genome-wide in vivo screen for protein-protein interactions in Saccharomyces cerevisiae by means of a protein-fragment complementation assay (PCA). We identified 2770 interactions among 1124 endogenously expressed proteins. Comparison with previous studies confirmed known interactions, but most were not known, revealing a previously unexplored subspace of the yeast protein interactome. The PCA detected structural and topological relationships between proteins, providing an 8-nanometer-resolution map of dynamically interacting complexes in vivo and extended networks that provide insights into fundamental cellular processes, including cell polarization and autophagy, pathways that are evolutionarily conserved and central to both development and human health.