The purplish bifurcate mussel Mytilisepta virgata is widely distributed and represents one of the major components of the intertidal community in the northwestern Pacific (NWP). Here, we characterized population genetic structure of NWP populations throughout their whole distribution range using both mitochondrial (mtDNA cox1) and nuclear (ITS1) markers. Population genetic analyses for mtDNA cox 1 sequences revealed two monophyletic lineages (i.e., southern and northern lineages) geographically distributed according to the two different surface water temperature zones in the NWP. The timing of the lineage split is estimated at the Pliocene- mid-Pleistocene (5.49-1.61 Mya), which is consistent with the timing of the historical isolation of the East Sea/Sea of Japan from the South and East China Seas caused by sea level decline during glacial cycles. Historical sea level fluctuation during the Pliocene-Pleistocene and subsequent adaptation of mussels to different surface water temperature zones may have contributed to shaping the contemporary genetic diversity and deep divergence of the two mitochondrial lineages. Unlike mtDNA sequences, a clear lineage splitting between the two mitochondrial lineages was not found in ITS1 sequences, showing a star-like structure that is composed of a mixture of southern and northern mitochondrial lineages. Possible scenarios are proposed to explain this type of mito-nuclear discordance: stochastic divergence in the coalescent processes of the two molecular markers, or balancing selection under different marine environments. Future work is required to address whether the thermal physiology of these mussels correlates with the deep divergence of their mitochondrial genes.