Seminal fluid proteins transferred from males to females during copulation are required for full fertility and can exert dramatic effects on female physiology and behavior. In Drosophila melanogaster, the seminal protein sex peptide (SP) affects mated females by increasing egg production and decreasing receptivity to courtship. These behavioral changes persist for several days because SP binds to sperm that are stored in the female. SP is then gradually released, allowing it to interact with its female-expressed receptor. The binding of SP to sperm requires five additional seminal proteins, which act together in a network. Hundreds of uncharacterized male and female proteins have been identified in this species, but individually screening each protein for network function would present a logistical challenge. To prioritize the screening of these proteins for involvement in the SP network, we used a comparative genomic method to identify candidate proteins whose evolutionary rates across the Drosophila phylogeny co-vary with those of the SP network proteins. Subsequent functional testing of 18 co-varying candidates by RNA interference identified three male seminal proteins and three female reproductive tract proteins that are each required for the long-term persistence of SP responses in females. Molecular genetic analysis showed the three new male proteins are required for the transfer of other network proteins to females and for SP to become bound to sperm that are stored in mated females. The three female proteins, in contrast, act downstream of SP binding and sperm storage. These findings expand the number of seminal proteins required for SP's actions in the female and show that multiple female proteins are necessary for the SP response. Furthermore, our functional analyses demonstrate that evolutionary rate covariation is a valuable predictive tool for identifying candidate members of interacting protein networks.