The Oriental fire-bellied toad (Bombina orientalis) is a commonly used study organism, but knowledge of its evolutionary history is incomplete. We analyze sequence data from four genetic markers (mtDNA genes encoding cytochrome c oxidase subunit I, cytochrome b, and 12S–16S rRNA; nuDNA gene encoding recombination activating gene 2) from 188 individuals across its range in Northeast Asia to elucidate phylogeographic patterns and to identify the historic events that shaped its evolutionary history. Although morphologically similar across its range, B. orientalis exhibits phylogeographic structure, which we infer was shaped by geologic, climatic, and anthropogenic events. Phylogenetic and divergence-dating analyses recover four genetically distinct groups of B. orientalis: Lineage 1—Shandong Province and Beijing (China); Lineage 2—Bukhan Mountain (Korea); Lineage 3—Russia, Northeast China, and northern South Korea; and Lineage 4—South Korea. Lineage 2 was previously unknown. Additionally, we discover an area of secondary contact on the Korean Peninsula, and infer a single dispersal event as the origin of the insular Jeju population. Skyline plots estimate different population histories for the four lineages: Lineages 1 and 2 experienced population decreases, Lineage 3 remained stable, while Lineage 4 experienced a sharp increase during the Holocene. The timing of the population expansion of Lineage 4 coincides with the advent of rice cultivation, which may have facilitated the increase in population size by providing additional breeding habitat.