Littorina brevicula is one of the most common gastropods in the supralittoral zone around Japan. The northernmost population of this species is around Hokkaido and the determinant of this northern limit is likely seawater and air temperature. To reconstruct an evolutionary history of this species, we investigated genetic differentiation among 12 populations (three from Hokkaido, six from Honshu and three from Kyushu) using a mitochondrial DNA marker (partial sequence of the NADH dehydrogenase 6 gene). The haplotype network showed shallow genetic divergence within the species, suggesting a bottleneck followed by population expansion. One major haplotype that occurred in 70.5% of all individuals examined was the most frequent in every population sampled. A second major haplotype was abundant around Kyushu but not found in Hokkaido. This skewed haplotype distribution resulted in significant genetic differentiation along the north-south axis of Japan. The importance of the southern clade, which included the second major haplotype, was supported by population genetic analyses of datasets that excluded either the southern clade or the northern clades. The north-south differentiation remained when datasets that excluded the northern clades were used, but disappeared when datasets that excluded the southern clade were used. The combined evidence of shallow divergence and the north-south population structure suggests that the L. brevicula population around Japan once declined and then expanded and colonized northward. Although the time of population reduction and recolonization could not be precisely estimated, the observation that this species is absent further north in Japan suggests that it would have been unable to survive in northern Japan during the last glacial maximum (LGM) and therefore recolonization likely occurred after the LGM, probably from south to north.