A membrane-spanning heptad repeat motif mediates interaction between transmembrane segments. This motif was randomized with three different sets of mostly hydrophobic residues in the context of POSSYCCAT, a modified ToxR transcription activator system. The resulting combinatorial libraries were subjected to different levels of selective pressure to obtain groups of transmembrane segments that are distinguished by their ability to self-interact in bacterial membranes. Upon relating self-interaction to amino acid composition, the following conclusions were made. First, randomization with only Leu, Ile, Val, Met, and Phe resulted in unexpected robust self-interaction with little sequence specificity. Second, with more complex amino acid mixtures that represent natural transmembrane segments more closely, self-interaction critically depended on amino acid composition of the interface. Whereas the contents of Ile and Leu residues increased with the ability to self-interact, the contents of Pro and Arg residues decreased. Third, heptad repeat motifs composed of Leu, Ile, Val, Met, and Phe were approximately 40-fold over-represented in transmembrane segments of single-span membrane proteins as compared with motifs composed of the more complex amino acid mixtures. This suggests that heptad motifs composed of the smaller subset of amino acids were enriched in the course of natural single-span membrane protein evolution.