Due to its pivotal geographical location and proximity to transcontinental migratory routes, Iran has played a key role in subsequent migrations, both prehistoric and historic, between Africa, Asia and Europe. To shed light on the genetic structure of the Iranian population as well as on the expansion patterns and population movements which affected this region, the complete mitochondrial genomes of 352 Iranians were obtained. All Iranian populations studied here exhibit similarly high diversity values comparable to the other groups from the Caucasus, Anatolia and Europe. The results of AMOVA and MDS analyses did not associate any regional and/or linguistic group of populations in the Anatolia/Caucasus and Iran region pointing to close genetic positions of Persians and Qashqais to each other and to Armenians, and Azeris from Iran to Georgians. By reconstructing the complete mtDNA phylogeny of haplogroups R2, N3, U1, U3, U5a1g, U7, H13, HV2, HV12, M5a and C5c we have found a previously unexplored genetic connection between the studied Iranian populations and the Arabian Peninsula, India, Near East and Europe, likely the result of both ancient and recent gene flow. Our results for Persians and Qashqais point to a continuous increase of the population sizes from ∼24 kya to the present, although the phase between 14-24 kya is thought to be hyperarid according to the Gulf Oasis model. Since this would have affected hunter-gatherer ranges and mobility patterns and forced them to increasingly rely on coastal resources, this transition can explain the human expansion across the Persian Gulf region.