Co-evolution is a major driving force shaping the outcome of host-parasite interactions over time. After host shifts, the lack of co-evolution can have a drastic impact on novel host populations. Nevertheless, it is known that Western honey bee (Apis mellifera) populations can cope with host-shifted ectoparasitic mites (Varroa destructor) by means of natural selection. However, adaptive phenotypic traits of the parasites and temporal variations in host resistance behavior are poorly understood. Here, we show that mites made adaptive shifts in reproductive strategy when associated with resistant hosts and that host resistance traits can change over time. In a fully-crossed field experiment, worker brood cells of local adapted and non-adapted (control) A. mellifera host colonies were infested with mites originating from both types of host colonies. Then, mite reproduction as well as recapping of cells and removal of infested brood (i.e., Varroa Sensitive Hygiene, VSH) by host workers were investigated and compared to data from the same groups of host colonies three years earlier. The data suggest adaptive shifts in mite reproductive strategies, because mites from adapted hosts have higher probabilities of reproduction, but lower fecundity, when infesting their associated hosts than mites in treated colonies. The results confirm that adapted hosts can reduce mite reproductive success. However, neither recapping of cells nor VSH were significantly expressed, even though the latter was significantly expressed in this adapted population three years earlier. This suggests temporal variation in the expression of adaptive host traits. It also appears as if mechanisms not investigated here were responsible for the reduced mite reproduction in the adapted hosts. In conclusion, a holistic view including mite adaptations and studies of the same parasite/host populations over time appears overdue to finally understand the mechanisms enabling survival of V. destructor-infested honey bee host colonies.