Recent molecular studies have indicated that phylogeographical history of Japanese biota is likely shaped by geohistory along with biological events, such as distribution shifts, isolation, and divergence of populations. However, the genetic structure and phylogeographical history of terrestrial Annelida species, including leech species, are poorly understood. Therefore, we aimed to understand the genetic structure and phylogeographical history across the natural range of Haemadipsa japonica, a sanguivorous land leech species endemic to Japan, by using nine polymorphic nuclear microsatellites (nSSR) and cytochrome oxidase subunit one (COI) sequences of mitochondrial DNA (mtDNA). Analyses using nSSR revealed that H. japonica exhibited a stronger regional genetic differentiation among populations (G'ST = 0.77) than other animal species, probably because of the low mobility of land leech. Analyses using mtDNA indicated that H. japonica exhibited two distinct lineages (A and B), which were estimated to have diverged in the middle Pleistocene and probably because of range fragmentation resulting from climatic change and glacial and interglacial cycles. Lineage A was widely distributed across Japan, and lineage B was found in southwestern Japan. Analyses using nSSR revealed that lineage A was roughly divided into two population groups (i.e., northeastern and southwestern Japan); these analyses also revealed a gradual decrease in genetic diversity with increasing latitude in lineage A and a strong genetic drift in populations of northeastern Japan. Combined with the largely unresolved shallow polytomies from the mtDNA phylogeny, these results implied that lineage A may have undergone a rapid northward migration, probably during the Holocene. Then, the regional genetic structure with local unique gene pools may have been formed within each lineage because of the low mobility of this leech species.