Abstract Background Maps depicting binary interactions between proteins can be powerful starting points for understanding biological systems. A proven technology for generating such maps is high-throughput yeast two-hybrid screening. In the most extensive screen to date, a Gal4-based two-hybrid system was used recently to detect over 20,000 interactions among Drosophila proteins. Although these data are a valuable resource for insights into protein networks, they cover only a fraction of the expected number of interactions. Results To complement the Gal4-based interaction data, we used the same set of Drosophila open reading frames to construct arrays for a LexA-based two-hybrid system. We screened the arrays using a novel pooled mating approach, initially focusing on proteins related to cell-cycle regulators. We detected 1,814 reproducible interactions among 488 proteins. The map includes a large number of novel interactions with potential biological significance. Informative regions of the map could be highlighted by searching for paralogous interactions and by clustering proteins on the basis of their interaction profiles. Surprisingly, only 28 interactions were found in common between the LexA- and Gal4-based screens, even though they had similar rates of true positives. Conclusions The substantial number of new interactions discovered here supports the conclusion that previous interaction mapping studies were far from complete and that many more interactions remain to be found. Our results indicate that different two-hybrid systems and screening approaches applied to the same proteome can generate more comprehensive datasets with more cross-validated interactions. The cell-cycle map provides a guide for further defining important regulatory networks in Drosophila and other organisms.