Specific interactions of transmembrane helices play a pivotal role in the folding and oligomerization of integral membrane proteins. The helix–helix interfaces frequently depend on specific amino acid patterns. In this study, a heptad repeat pattern was randomized with all naturally occurring amino acids to uncover novel sequence motifs promoting transmembrane domain interactions. Self-interacting transmembrane domains were selected from the resulting combinatorial library by means of the ToxR/POSSYCCAT system. A comparison of the amino acid composition of high-and low-affinity sequences revealed that high-affinity transmembrane domains exhibit position-specific enrichment of histidine. Further, sequences containing His preferentially display Gly, Ser, and/or Thr residues at flanking positions and frequently contain a C-terminal GxxxG motif. Mutational analysis of selected sequences confirmed the importance of these residues in homotypic interaction. Probing heterotypic interaction indicated that His interacts in trans with hydroxylated residues. Reconstruction of minimal interaction motifs within the context of an oligo-Leu sequence confirmed that His is part of a hydrogen bonded cluster that is brought into register by the GxxxG motif. Notably, a similar motif contributes to self-interaction of the BNIP3 transmembrane domain.