Successful reproduction depends on interactions between numerous proteins beyond those involved directly in gamete fusion. Although such reproductive proteins evolve in response to sexual selection pressures, how networks of interacting proteins arise and evolve as reproductive phenotypes change remains an open question. Here, we investigated the molecular evolution of the 'sex peptide network' of Drosophila melanogaster, a functionally well-characterized reproductive protein network. In this species, the peptide hormone sex peptide (SP) and its interacting proteins cause major changes in female physiology and behaviour after mating. In contrast, females of more distantly related Drosophila species do not respond to SP. In spite of these phenotypic differences, we detected orthologs of all network proteins across 22 diverse Drosophila species and found evidence that most orthologs likely function in reproduction throughout the genus. Within SP-responsive species, we detected the recurrent, adaptive evolution of several network proteins, consistent with sexual selection acting to continually refine network function. We also found some evidence for adaptive evolution of several proteins along two specific phylogenetic lineages that correspond with increased expression of the SP receptor in female reproductive tracts or increased sperm length, respectively. Finally, we used gene expression profiling to examine the likely degree of functional conservation of the paralogs of an SP network protein that arose via gene duplication. Our results suggest a dynamic history for the SP network in which network members arose before the onset of robust SP-mediated responses and then were shaped by both purifying and positive selection.