We investigated the population dynamics of a highly clonal marine angiosperm, Cymodocea nodosa, in the eastern Mediterranean Sea, to identify the historical dynamics, demography, and connectivity of the species in the area. Eighteen microsatellite loci were used in conjunction with coalescent methods to investigate the genetic structure and demographic history of C. nodosa meadows. Approximate Bayesian computation (ABC) modeling was used to examine the pattern of divergence over time in the context of environmental change over the course of the Quaternary period. ABC analysis revealed an initial split of the C. nodosa populations between the north-western, northern, and north-eastern Aegean Sea during the Pleistocene epoch, followed by a more recent divergence of the north-western population and the central-western part of the Aegean Sea. According to the results, the most parsimonious historical scenario is that of a pervasive genetic signature of the effects of the drop in sea level during the Pleistocene epoch. This scenario supports the isolation of the north-western, north, and north-eastern area, and the subsequent recolonization after post-glaciation sea level rise that may explain the north-western differentiation as well present-day detected dispersion of C. nodosa.