The sugi bark borer, Semanotus japonicus, occurs naturally in Honshu, Shikoku, Sado Is., Oki Is., and Yaku Is. in Japan, and its main host tree is the Japanese cedar, Cryptomeria japonica. Because the geographical structure of the morphological characters largely corresponds to the sites of the glacial refugia and the post-Pleistocene dispersal route of the Japanese cedar, the history of the cedar was postulated to have shaped the genetic population structure in the borer. In this study, we used partial sequences from mitochondrial DNA genes, the COI, tRNALeu-UUR and COII to elucidate processes in the geographical structuring of S. japonicus populations. Ten haplotypes were revealed among 52 individuals from four populations that ranged from Iwate to Ehime prefectures. The geographical distribution of these haplotypes was highly structured. Two distinct lineages were detected, which probably represented the Pacific coastal and the Japan Sea side lineages, from the neighbour-joining method and haplotype networking. As haplotypes of both Pacific and Japan Sea lineages were found in the Iwate population, a second contact might have occurred in the Tohoku area. These results suggested that the present genetic structure of S. japonicus was determined by the host’s past history.