The ectoparasitic mite Varroa destructor is the most significant pathological threat to the western honey bee, Apis mellifera, leading to the death of most colonies if left untreated. An alternative approach to chemical treatments is to selectively enhance heritable honey bee traits of resistance or tolerance to the mite through breeding programs, or select for naturally surviving untreated colonies. We conducted a literature review of all studies documenting traits of A. mellifera populations either selectively bred or naturally selected for resistance and tolerance to mite parasitism. This allowed us to conduct an analysis of the diversity, distribution and importance of the traits in different honey bee populations that can survive V. destructor globally. In a second analysis, we investigated the genetic bases of these different phenotypes by comparing ’omics studies (genomics, transcriptomics, and proteomics) of A. mellifera resistance and tolerance to the parasite. Altogether, this review provides a detailed overview of the current state of the research projects and breeding efforts against the most devastating parasite of A. mellifera. By highlighting the most promising traits of Varroa-surviving bees and our current knowledge on their genetic bases, this work will help direct future research efforts and selection programs to control this pest. Additionally, by comparing the diverse populations of honey bees that exhibit those traits, this review highlights the consequences of anthropogenic and natural selection in the interactions between hosts and parasites.