Biologists have long noted the tremendous diversity of behaviors, morphological traits and molecules involved in mating and reproduction. In this thesis, I investigate the molecular evolution of reproductive proteins in the vinegar fly Drosophila melanogaster, focusing on a class of ejaculate proteins known as accessory gland proteins (?Acps?). Previous work has documented extensive evidence for rapid, adaptive evolution of some Acps. It is generally thought that male-female interactions, e.g., sexual conflict and cryptic female choice, drive rapid Acp evolution, although evidence specifically favoring this hypothesis in D. melanogaster is limited. Here, I describe biochemical and structural studies on a particularly rapidly evolving Acp, ovulin. I argue that structural features of ovulin may contribute to its ability to tolerate high sequence diversity. I also investigate the molecular evolution of a class of Acps and female reproductive tract proteins that (I argue) are particularly likely to undergo co-evolution between males and females, namely proteolysis regulators and targets of proteolysis. I show that a number of proteolysis regulators and targets are subject to positive selection, and find evidence of male-female co-evolution. Finally, I critically examine an underlying assumption of many divergence based methods for inferring positive selection ? the assumption of phylogenetic congruence between loci. I find that, within the genus Drosophila, at least two nodes show evidence for phylogenetic incongruence, possibly due to incomplete ancestral lineage sorting.