Many integral membrane proteins assemble to form oligomeric structures in biological membranes. In particular, seven-transmembrane helical G protein-coupled receptors (GPCRs) appear to self-assemble constitutively in membranes, but the mechanism and physiological role of this assembly are unknown. We developed and employed coarse-grain molecular dynamics (CGMD) models to investigate the molecular basis of how the physicochemical properties of the phospholipid bilayer membrane affect self-assembly of visual rhodopsin, a prototypical GPCR. The CGMD method is a mesoscopic simulation technique in which groups of atoms are mapped to particles on the basis of a four-to-one rule. This systematic reduction of the degrees of freedom allows for computationally efficient calculation of the structure and dynamics of molecular assemblies for larger time and length scales than accessible to atomistic models, providing here an unprecedented view of spontaneous protein assembly in biomembranes. Systems with up to 16 rhodopsin molecules at a protein-to-lipid ratio of 1:100 were simulated for time scales of up to 8 micros. The results obtained for four different phospholipid environments showed that localized adaptation of the membrane bilayer to the presence of receptors is reproducibly most pronounced near transmembrane helices 2, 4, and 7. This local membrane deformation appears to be a key factor defining the rate, extent, and orientational preference of protein-protein association. The implications of our findings are discussed within a framework of a generalized mechanism of membrane protein self-assembly.