The process of loss or gain of parasites during invasion of new lands is not well understood. The alfalfa weevil Hypera postica is an invasive pest of various leguminous crops and consists of three major mitochondrial haplotypes, ‘Western’, ‘Egyptian’ and ‘Eastern’. The Western strain is infected with the endosymbiotic proteobacteria Wolbachia, that cause unidirectional complete reproductive incompatibility, in its native (Europe) and an introduced (the United States) ranges. However, our preliminary screening of a few introduced populations in Northern Kyushu, southwestern Japan, failed to detect Wolbachia from the Western strain. A larger-scale and historical assessment of Wolbachia infection may allow to estimate when and how the bacteria were lost, and current geographical distribution of infection among host haplotypes. In this study, we aim to assess the Wolbachia-infection status of H. postica populations throughout Northern Kyushu, where H. postica invasion to Japan was first found. A total of 228 individuals from seven regions in Northern Kyushu collected in different time periods from 1982 to 2015 and 14 individuals from Europe were subjected to PCR diagnostics for Wolbachia. Wolbachia from the Western strain was not detected, irrespective of the time periods and geographic areas in Northern Kyushu. We found ‘Egyptian’-strain H. postica collected most recently from an island off Kyushu harboured a supergroup-B Wolbachia variant. This variant was genetically different from the European Wolbachia variant infecting Western-strain H. postica. The infection was new to the Egyptian haplotype and was estimated to have taken place independently of the loss in the Western strain.