Recent advances in evolutionary biology have highlighted the important roles of hybridization and gene flow in shaping genetic structure and diversification in many organisms. The Japanese fire-bellied newt, Cynops pyrrhogaster, comprises multiple diverged mitochondrial DNA (mtDNA) lineages. High genetic differentiation and strong reproductive isolation were observed among lineages, suggesting that some of these lineages may represent distinct species. To clarify the population structure and gene flow among lineages, we performed population genetic analyses based on genome-wide ddRAD-seq together with partial mitochondrial cytochrome-b sequences, using samples collected across the species’ entire geographic range. Analyses of SNP data revealed three major groups (Northern, Central, and Western groups) with some hybrid populations in the contact zones. Estimation of the evolutionary history using an approximate Bayesian computation (ABC) approach suggested that the common ancestor of this species first diverged into the Northern and Western groups in the late Miocene, and that subsequent hybridization between these two groups gave rise to the Central group in the late Pliocene. An f4-test indicated gene flow from the Western group into the southwestern Central group, as well as that from the Northern group into the northeastern Central group. A mito-nuclear discordant population was also detected within the southwestern Central group, suggesting past hybridization. These results demonstrate that hybridization and subsequent gene flow play a crucial role in the formation of complex population structure and the maintenance of genetic diversity in the Japanese fire-bellied newt.