Aphanius fasciatus is a small fish occurring in Mediterranean brackish environments. In Cyprus, it is known from three localities separated by long stretches of coast. The genetic diversity of these populations was evaluated using fragments of two mitochondrial genes. A comparison with the other available data showed that Cyprus populations represent a distinct lineage. The other lineages are concentrated in a relatively small area between the Strait of Sicily and the Western Ionian Sea, while all other areas include a subset of these lineages, suggesting that the aforementioned area might have acted as a glacial refugium. Landlocked North-African populations diverge from all other populations, suggesting that they might have originated in the Late Pleistocene, during transgression events of the Mediterranean Sea in North-African inland water bodies. The genetic diversity of A. fasciatus varied across different Cyprus populations, with a pattern mirroring the degree of environmental degradation, which likely affected population genetic variability through demographic reductions. The three Cyprus populations showed genetic uniqueness, suggesting the need for population-based management practices; the low genetic diversity of two populations, and the number of threats affecting them, suggest that the species should be considered endangered at the national level, and deserves protection measures.