We describe one of the first attempts at unrestrained modeling of self-association of α-helices in implicit heterogeneous membrane-mimic media. The computational approach is based on the Monte Carlo conformational search for peptides in dihedral angles space. The membrane is approximated by an effective potential. The method is tested in calculations of two hydrophobic segments of human glycophorin A (GpA), known to form membrane-spanning dimers in real lipid bilayers. Our main findings may be summarized as follows. Modeling in vacuo does not adequately describe the behavior of GpA helices, failing to reproduce experimental structural data. The membrane environment stabilizes α-helical conformation of GpA monomers, inducing their transmembrane insertion and facilitating interhelical contacts. The voltage difference across the membrane promotes "head-to-head" orientation of the helices. "Fine-tuning" of the monomers in a complex is shown to be regulated by van der Waals interactions. Detailed exploration of conformational space of the system starting from arbitrary locations of two noninteracting helices reveals only several groups of energetically favorable structures. All of them represent tightly packed transmembrane helical dimers. In overall, they agree reasonably well with mutagenesis data, some of them are close to NMR-derived structures. A possibility of left-handed dimers is discussed. We assume that the observed moderate structural heterogeneity (the existence of several groups of states with close energies) reflects a real equilibrium dynamics of the monomers-at least in membrane mimics used in experimental studies of GpA. The elaborated computational approach is universal and may be employed in studies of a wide class of membrane peptides and proteins. © 2005 American Chemical Society.