Using complete sequences of cytochrome b (cyt b) and control region (CR; D-loop) genes of mitochondrial DNA, we investigated the phylogenetic relationships and phylogeography among populations of the salamander Hynobius tokyoensis in northern Japan. Inclusion of populations from Aichi, Chubu region within Hynobius nebulosus by previous results was confirmed because they formed a clade with H. nebulosus. Monophyly of H. tokyoensis was supported in all trees analyzed, and two clades consistently emerged: clade A from northeastern Kanto (Ibaraki) to southern Tohoku (Fukushima), and clade B from the remaining area south of northern Kanto (Tochigi). These two clades are estimated to have an old history of divergence during the late Pliocene, when the present-day Kanto Plain was under the sea. Within clade B, three haplotypes groups (I-III) are hypothesized to have diverged more recently, i.e., between the early and mid-Pleistocene, probably in relation to glacial events. The ancestral groups I and II were separated at the present-day western Kanto and Boso Peninsula areas, respectively, and subsequently, group II invaded northward to the present-day northern Kanto area and gave rise to group III. Populations of the Miura Peninsula are thought to have multiple origins, one directly from Boso and another from a more recent southward invasion from the northern Kanto area. Cytochrome b appears to have evolved more quickly than CR genes in H. tokyoensis, and thus will be more useful for phylogenetic analyses and formulating conservation measures.