Plecoglossus altivelis (ayu) is an amphidromous fish widely distributed in Northeastern Asia from the East China Sea to the northern Japanese coastal waters, encompassing the Korean Peninsula within its range. The shore lines of northeastern region in Asia have severely fluctuated following glaciations in the Quaternary. In the present study, we investigate the population genetic structure and historical demographic change of P. altivelis at a population level in East Asia. Analysis of molecular variance (AMOVA) based on 244 mitochondrial control region DNA sequences clearly showed that as the sampling scope extended to a larger geographic area, genetic differentiation began to become significant, particularly among Northeastern populations. A series of hierarchical AMOVA could detect the genetic relationship of three closely located islands between Korea and Japan that might have been tightly connected by the regional Tsushima current. Neutrality and mismatch distribution analyses revealed a strong signature of a recent population expansion of P. altivelis in East Asia, estimated at 126 to 391 thousand years ago during the late Pleistocene. Therefore it suggests that the present population of P. altivelis traces back to its approximate demographic change long before the last glacial maximum. This contrasts our a priori expectation that the most recent glacial event might have the most crucial effect on the present day demography of marine organisms through bottleneck and subsequent increase of effective population size in this region.