In order to investigate the phylogeography and population genetic structure of the South European toothcarp (Aphanius fasciatus), we analysed gene sequences of two mitochondrial markers (cytochrome b and mtDNA control region) in samples from eight localities along the eastern Adriatic coast and combined them with sequences from other Mediterranean localities. Since the South European toothcarp primarily inhabits hypersaline water bodies, it is a good model species for understanding patterns of colonization and dispersal of species adapted to variable conditions. The eastern Adriatic populations are separated into two groups of genetically related populations. The Northern group contains the populations from Sečovlje, Pag, Dinjiška, Nin and Pantan, whereas the Southern group contains the populations from Ston, Ulcinj and Narta. The majority of divergence events date back to the Pleistocene epoch and it is likely that sea level changes during glacial cycles played a significant role in shaping the recent genetic structure of this species. Our results imply pronounced intraspecific structuring of this species, whereas great environmental variations resulted in a smaller intrapopulational genetic diversity of A. fasciatus than seen in other Mediterranean fishes.