In polygynous mammals, most variance in male reproductive success is expected to result from competition between males, and the role of female behavior remains poorly understood. Contests between red deer males during the annual rut are one of the most famous examples of male-male competition. However, anecdotal evidence suggests females in estrus make substantial movements, changing harems, and potentially disrupting the outcome of male contests. In other polygynous mammals, such movements have been interpreted as evidence of female mating preferences. Here, we use 34 years of detailed observational data on wild red deer to show that 43% of estrous females are found in different harems between successive observations and that 64% of such females make substantial movements (up to 4 km) when this occurs. Approximately 45% of these movements result in the male into whose harem a female moved fathering her offspring. We then test whether females move nonrandomly with respect to male phenotype, consistent with the hypothesis that females move to mate with preferred males. Although in general, females were more likely to be found in larger harems and the harems of younger males after harem changes, these effects were not specific to estrous females. Further, estrous females were not more likely to be found in the harems of less related males. We therefore find little support for the idea that estrous females move between harems to mate with a preferred male; as a result, the reasons females make such extraordinary movements when in estrus remain unclear.