Yeast two-hybrid (Y2H) has been successfully used for genome-wide screens to identify protein-protein interactions for several model organisms. Nonetheless, the logistics of pair-wise screening has resulted in a cumbersome and incomplete application of this method to complex genomes. Here, we develop a modification of Y2H that eliminates the requirement for pair-wise screening. This is accomplished by incorporating lox sequences into Y2H vectors such that cDNAs encoding interacting partners become physically linked in the presence of Cre recombinase in vivo. Once linked, DNA from complex pools of clones can be processed without losing the identity of the interacting partners. Short linked sequence tags from each pair of interacting partner (binary interaction Tags or BI-Tags) are then recovered and sequenced. To validate the approach, comparisons between interactions found using traditional Y2H and the BI-Tag method were made, which demonstrate that the BI-Tag technology accurately represents the complexity of the interaction partners found in the screens. The technology described here sufficiently improves the throughput of the Y2H approach to make feasible the generation of near comprehensive interaction maps for complex organisms.