Wolbachia are obligatory endosymbiotic α-proteobacteria found in many arthropods. They are maternally inherited, and can induce reproductive alterations in the hosts. Despite considerable recent progress in studies on the associations between Wolbachia and various taxonomic groups of insects, none of the researches have revealed the effects of Wolbachia on longicorn beetles as the host insect. Acalolepta fraudatrix is a forest longicorn beetle that is distributed in East Asia. In this study, the relationship between Wolbachia and A. fraudatrix was investigated. Out of two populations of A. fraudatrix screened for Wolbachia using the genes ftsZ, wsp, and 16S rRNA, only one of the populations showed detection of all three genes indicating the presence of Wolbachia. Electron microscopy and fluorescent in situ hybridization also confirmed that the A. fraudatrix population was infected with Wolbachia. Sequencing the wsp genes derived from single insects revealed that two strains of Wolbachia coexisted in the insects based on the detection of two different sequences of the wsp gene. We designated these strains as wFra1 and wFra2. The bacterial titers of wFra1 were nearly 2-fold and 3-fold higher than wFra2 in the testes and ovaries, respectively. The two strains of Wolbachia in the insects were completely eliminated by rearing the insects on artificial diets containing 1% concentration of tetracycline for 1 generation. Reciprocal crosses between Wolbachia-infected and Wolbachia-uninfected A. fraudatrix demonstrated that only eggs produced by the crosses between Wolbachia-infected males and Wolbachia-uninfected females did not hatch, indicating that Wolbachia infecting A. fraudatrix causes cytoplasmic incompatibility in the host insect. This is the first report showing the effect of Wolbachia on reproductive function in a longicorn beetle, A. fraudatrix.