The small air-breathing fish, Channa gachua, is distributed in the shallow regions of the streams and rivers of Yunnan Province and Hainan Island in China. At present, there are limited studies on the genetic differentiation and phylogeography of C. gachua. To understand the genetic diversity of C. gachua and determine how the geological events and climatic changes have influenced the phylogeographic structures and evolutionary history of this species, 168 specimens were collected from 6 populations in 6 drainages (Changhua, Lingshui, Tengqiao, Wanquan, Nandu, and Red rivers) in Hainan Island and Yunnan province, using the mitochondrial DNA cytochrome b gene (1142 bp) as a molecular marker. The phylogenetic tree showed two major lineages (A and B). Lineage A included all samples from Hainan Island. Among them, some samples of the Changhua River fell into an independent subclade (A2), and the remaining samples were clustered into another subclade (A1); Lineage B contained all samples from the Red River. The genetic differentiation index of C. gachua among the different lineages was high. The demographic history indicated that the total populations, lineage A1, A2, and B have not undergone recent expansion. Bayesian skyline plots showed that the effective population size of lineage A1 and B declined at 0.01 millions of years ago. According to our research, during Pleistocene glaciations, the Gulf of Tonkin was exposed owing to a drop in sea level. The drainages in the mainland and Hainan Island were in contact. Drainages in northern Vietnam (including the Red River) flowed into the South China Sea by a paleochannel connecting the Leizhou Peninsula and Hainan Island. At this time, the exposure of the Gulf of Tonkin gave C. gachua a chance for population dispersion between the Red River and southwestern Hainan Island drainage, and subsequently enhanced gene flow between populations in the Hainan Island drainages.