Drosophila melanogaster females commonly mate with multiple males establishing the opportunity for pre- and postcopulatory sexual selection. Traits impacting sexual selection can be affected by a complex interplay of the genotypes of the competing males, the genotype of the female, and compatibilities between the males and females. We scored males from 96 2nd and 94 3rd chromosome substitution lines for traits affecting reproductive success when mated with females from 3 different genetic backgrounds. The traits included male-induced female refractoriness, male remating ability, the proportion of offspring sired under competitive conditions and male-induced female fecundity. We observed significant effects of male line, female genetic background, and strong male by female interactions. Some males appeared to be “generalists” and performed consistently across the different females; other males appeared to be “specialists” and performed very well with a particular female and poorly with others. “Specialist” males did not, however, prefer to court those females with whom they had the highest reproductive fitness. Using 143 polymorphisms in male reproductive genes, we mapped several genes that had consistent effects across the different females including a derived, high fitness allele in Acp26Aa that may be the target of adaptive evolution. We also identified a polymorphism upstream of PebII that may interact with the female genetic background to affect male-induced refractoriness to remating. These results suggest that natural variation in PebII might contribute to the observed male-female interactions.