The drivers of population differentiation in oceanic dispersal organisms have been crucial for research in evolutionary biology. Adaptation to different environments is commonly invoked as an alternative to geographic isolation, as a driver of differentiation in the oceans. In this study, we investigate the population structure and phylogeography of the bottlenose dolphin (Tursiops truncatus) in the Mediterranean Sea, using microsatellite loci and the entire mtDNA control region. By further comparing the Mediterranean populations with the well described Atlantic populations, we addressed the following hypotheses: 1) bottlenose dolphins show population structure within the environmentally complex Eastern Mediterranean Sea; 2) population structure was gained locally or otherwise results from chance distribution of pre-existing genetic structure; 3) strong demographic variations within the Mediterranean basin have affected genetic variation sufficiently to bias detected patterns of population structure. Our results suggest that bottlenose dolphin exhibits population structures that correspond well to the main Mediterranean basins. Furthermore, we found evidence for fine scale population division within the Adriatic and the Levantine seas. We further describe for the first time, a distinction between populations inhabiting pelagic and coastal regions within the Mediterranean. Phylogeographic analysis, suggests that current genetic structure results mostly from stochastic distribution of Atlantic genetic variation, resulting from a recent post-glacial expansion. Comparison with Atlantic mtDNA haplotypes, further suggest the existence of a metapopulation across North Atlantic/Mediterranean, with pelagic regions acting as source for coastal environments.