Population genetics of invading pests can be informative for understanding their ecology. In this study, we investigated population genetics of the invasive alfalfa weevil Hypera postica in Fukuoka Prefecture, Japan. We analyzed mitochondrial tRNA(Leu)-COII, nuclear EF-1 alpha gene fragments, and Wolbachia infection in relation to three leguminous host plants: Vicia angustifolia, Vicia villosa, and a new host Astragalus sinicus cultivated as a honey source and green manure crop. A parsimony network generated from mitochondrial gene sequences uncovered two major haplotypic groups, Western and Egyptian. In contrast to reported Wolbachia infection of the Western strain in the United States, none of our analyzed individuals were infected. The absence of Wolbachia may contribute to the stable coexistence of mitochondrial strains through inter-strain reproductive compatibility. Hypera postica genetic variants for the mitochondrial and nuclear genes were associated neither with host plant species nor with two geographic regions (Hisayama and Kama) within Fukuoka. Mitochondrial haplogroups were incongruent with nuclear genetic variants. Genetic diversity at the nuclear locus was the highest for the populations feeding on V. angustifolia. The nuclear data for A. sinicus-feeding populations indicated past sudden population growth and extended Bayesian skyline plot analysis based on the mitochondrial and nuclear data showed that the growth of A. sinicus-feeding population took place within the past 1000 years. These results suggest a shorter history of A. sinicus as a host plant compared with V. angustifolia and a recent rapid growth of H. postica population using the new host A. sinicus.