Macromolecular assemblies involving membrane proteins (MPs) serve vital biological roles and are prime drug targets in a variety of diseases. Large-scale affinity purification studies of soluble-protein complexes have been accomplished for diverse model organisms, but no global characterization of MP-complex membership has been described so far. Here we report a complete survey of 1,590 putative integral, peripheral and lipid-anchored MPs from Saccharomyces cerevisiae, which were affinity purified in the presence of non-denaturing detergents. The identities of the co-purifying proteins were determined by tandem mass spectrometry and subsequently used to derive a high-confidence physical interaction map encompassing 1,726 membrane protein-protein interactions and 501 putative heteromeric complexes associated with the various cellular membrane systems. Our analysis reveals unexpected physical associations underlying the membrane biology of eukaryotes and delineates the global topological landscape of the membrane interactome.