Traditionally it was thought that fitness-related traits such as male mating frequency, with a history of strong directional selection, should have little additive genetic variance and thus respond asymmetrically to bidirectional artificial selection. However, recent findings and theory suggest that a balance between selection for increased male mating frequency and opposing selection pressures on physiologically linked traits will cause male mating frequency to have high additive genetic variation and hence respond symmetrically to selection. We tested these hypotheses in the stalk-eyed fly, Cyrtodiopsis dalmanni, in which males hold harems comprising many females and so have the opportunity to mate at extremely high frequencies. We subjected male stalk-eyed flies to artificial selection for increased (‘high’) and decreased (‘low’) mating frequency in the presence of ecologically realistic, high numbers of females. High line males mated significantly more often than control or low line males. The direct response to selection was approximately symmetric in the high and low lines, revealing high additive genetic variation for, and no significant genetic constraints on, increased male mating frequency in C. dalmanni. In order to investigate trade-offs that might constrain male mating frequency under natural conditions we examined correlated responses to artificial selection. We measured accessory gland length, testis length and eyespan after 7 and 14 generations of selection. High line males had significantly larger accessory glands than low line males. No consistent correlated responses to selection were found in testis length or eyespan. Our results suggest that costs associated with the production and maintenance of large accessory glands, although yet to be identified, are likely to be a major constraint on mating frequency in natural populations of C. dalmanni.