Novel heterodimeric coiled-coil pairs were selected simultaneously from two DNA libraries using an in vivo protein-fragment complementation assay with dihydrofolate reductase, and the best pair was biophysically characterized. We randomized the interface-flanking e and g positions to Gln, Glu, Arg or Lys, and the core a position to Asn or Val in both helices simultaneously, using trinucleotide codons in DNA synthesis. Selection cycles with three different stringencies yielded sets of coiled-coil pairs, of which 80 clones were statistically analyzed. Thereby, properties most crucial for successful heterodimerization could be distinguished from those mediating more subtle optimization. A strong bias towards an Asn pair in the core a position indicated selection for structural uniqueness, and a reduction of charge repulsions at the e/g positions indicated selection for stability. Increased stringency led to additional selection for heterospecificity by destabilizing the respective homodimers. Interestingly, the best heterodimers did not contain exclusively complementary charges. The dominant pair, WinZip-A1B1, proved to be at least as stable in vitro as naturally occurring coiled coils, and was shown to be dimeric and highly heterospecific with a K(D) of approximately 24 nM. As a result of having been selected in vivo it possesses all characteristics required for a general in vivo heterodimerization module. The combination of rational library design and in vivo selection presented here is a very powerful strategy for protein design, and it can reveal new structural relationships.