Background: Variation in the non-coding regions of Y-chromosomes have been shown to influence gene regulation throughout the genome in some systems; a phenomenon termed Y-linked regulatory variation (YRV). This type of sex-specific genetic variance could have important implications for the evolution of male and female traits. If YRV contributes to the additive genetic variation of an autosomally coded trait shared between the sexes (e.g. body size), then selection could facilitate sexually dimorphic evolution via the Y-chromosome. In contrast, if YRV is entirely non-additive (i.e. interacts epistatically with other chromosomes), then Y-chromosomes could constrain trait evolution in both sexes whenever they are selected for the same trait value. The ability for this phenomenon to influence such fundamental evolutionary dynamics remains unexplored. Results: Here we address the evolutionary contribution of Y-linked variance by selecting for improved male geotaxis in populations possessing multiple Y-chromosomes (i.e. possessed Y-linked additive and/or epistatic variation) or a single Y-chromosome variant (i.e. possessed no Y-linked variation). We found that males from populations possessing Y-linked variation did not significantly respond to selection; however, males from populations with no Y-linked variation did respond. These patterns suggest the presence of a large quantity of Y-linked epistatic variance in the multi-Y population that dramatically slowed its response. Conclusions: Our results imply that YRV is unlikely to facilitate the evolution of sexually dimorphic traits (at least for the trait examined here), but can interfere with the rate of trait evolution in both males and females. This result could have real biological implications as it suggests that YRV can affect how quickly a population responds to new selective pressures (e.g. invasive species, novel pathogens, or climate change). Considering that YRV influences hundreds of genes and is likely typical of other independently-evolved hemizygous chromosomes, YRV-like phenomena may represent common and significant costs to hemizygous sex determination.