Interactions of transmembrane helices play a crucial role in the folding and oligomerisation of integral membrane proteins. In order to uncover novel sequence motifs mediating these interactions, we randomised one face of a transmembrane helix with a set of non-polar or moderately polar amino acids. Those sequences capable of self-interaction upon integration into bacterial inner membranes were selected by means of the ToxR/ POSSYCCAT system. A comparison between low/medium-affinity and high-affinity sequences reveals that high-affinity sequences are strongly enriched in phenylalanine residues that are frequently observed at the −3 position of GxxxG motifs, thus yielding FxxGxxxG motifs. Mutation of Phe or GxxxG in selected sequences significantly reduces self-interaction of the transmembrane domains without affecting their efficiency of membrane integration. Conversely, grafting FxxGxxxG onto unrelated transmembrane domains strongly enhances their interaction. Further, we find that FxxGxxxG is significantly over-represented in transmembrane domains of bitopic membrane proteins. The same motif contributes to self-interaction of the vesicular stomatitis virus G protein transmembrane domain. We conclude that Phe stabilises membrane-spanning GxxxG motifs. This is one example of how the role of certain side-chains in helix-helix interfaces is modulated by sequence context.