Host shifts of parasites are often causing devastating effects in the new hosts. The Varroa genus is known for a lineage of Varroa destructor that shifted to the Western honey bee, Apis mellifera, with disastrous effects on wild populations and the beekeeping industry. Despite this, the biology of Varroa spp. remains poorly understood in its native distribution range, where it naturally parasitizes the Eastern honey bee, Apis cerana. Here, we combined mitochondrial and nuclear DNA analyses with the assessment of mite reproduction to determine the population structure and host specificity of V. destructor and Varroa jacobsonii in Thailand, where both hosts and several Varroa species and haplotypes are sympatric. Our data confirm previously described mite haplogroups, and show three novel haplotypes. Multiple infestations of single host colonies by both mite species and introgression of alleles between V. destructor and V. jacobsonii suggest that hybridization occurs between the two species. Our results indicate that host specificity and population genetic structure in the genus Varroa is more labile than previously thought. The ability of the host shifted V. destructor haplotype to spillback to A. cerana and to hybridize with V. jacobsonii could threaten honey bee populations of Asia and beyond.