Wolbachia pipientis is a diverse, ubiquitous and most prevalent intracellular bacterial group of alpha-Proteobacteria that is concerned with many biological processes in arthropods. The coconut hispine beetle (CHB), Brontispa longissima (Gestro) is an economically important pest of palm cultivation worldwide. In the present study, we comprehensively surveyed the Wolbachia-infection prevalence and mitochondrial DNA (mtDNA) polymorphism in CHB from five different geographical locations, including China's Mainland and Taiwan, Vietnam, Thailand, Malaysia and Indonesia. A total of 540 sequences were screened in this study through three different genes, i.e., cytochrome oxidase subunit I (COI), Wolbachia outer surface protein (wsp) and multilocus sequencing type (MLST) genes. The COI genetic divergence ranges from 0.08% to 0.67%, and likewise, a significant genetic diversity (π = 0.00082; P = 0.049) was noted within and between all analyzed samples. In the meantime, ten different haplotypes (H) were characterized (haplotype diversity = 0.4379) from 21 different locations, and among them, H6 (46 individuals) have shown a maximum number of population clusters than others. Subsequently, Wolbachia-prevalence results indicated that all tested specimens of CHB were found positive (100%), which suggested that CHB was naturally infected with Wolbachia. Wolbachia sequence results (wsp gene) revealed a high level of nucleotide diversity (π = 0.00047) under Tajima's D test (P = 0.049). Meanwhile, the same trend of nucleotide diversity (π = 0.00041) was observed in Wolbachia concatenated MLST locus. Furthermore, phylogenetic analysis (wsp and concatenated MLST genes) revealed that all collected samples of CHB attributed to same Wolbachia B-supergroup. Our results strongly suggest that Wolbachia bacteria and mtDNA were highly concordant with each other and Wolbachia can affect the genetic structure and diversity within the CHB populations.