Geographic variations in the mitochondrial cytochrome b gene sequence (1,062 nucleotides) of the rocky intertidal goby Chaenogobius gulosus were examined and compared against the phylogeographic pattern of its sympatric sister species Chaenogobius annularis, which we studied previously. We collected C. gulosus specimens from 17 localities around the Japanese Archipelago and Korean Peninsula. Thirty-one haplotypes were obtained. The phylogenetic tree showed three geographical lineages, of which one was distributed along the coast of the Sea of Japan, suggesting that a Pleistocene isolation event in the Sea of Japan affected the genetic divergence of this species, similar to that which was observed in C. annularis. The net nucleotide divergence between the Sea of Japan and Pacific Ocean lineages in C. gulosus was much lower than that of C. annularis. Both traditional molecular clock and hierarchical approximate Bayesian computational models suggest that different divergence events affected the genetic divergences of C. gulosus and C. annularis. Our study on the sister species pair strongly supports multiple isolation events in the Sea of Japan, leading to varying levels of genetic divergence between the Pacific Ocean and Sea of Japan lineages in the Japanese coastal marine species.