It is now known that several population movements have taken place at different times throughout southern Arabian prehistory. One of the principal questions under debate is if the Early Holocene peopling of southern Arabia was mainly due to input from the Levant during the Pre-Pottery Neolithic B, to the expansion of an autochthonous population, or some combination of these demographic processes. Since previous genetic studies have not been able to include all parts of southern Arabia, we have helped fill this lacuna by collecting new population datasets from Oman (Dhofar) and Yemen (Al-Mahra and Bab el-Mandab). We identified several new haplotypes belonging to haplogroup R2 and generated its whole genome mtDNA tree with age estimates undertaken by different methods. R2, together with other considerably frequent southern Arabian mtDNA haplogroups (R0a, HV1, summing up more than 20% of the South Arabian gene pool) were used to infer the past effective population size through Bayesian skyline plots. These data indicate that the southern Arabian population underwent a large expansion already some 12 ka. A founder analysis of these haplogroups shows that this expansion is largely attributed to demographic input from the Near East. These results support thus the spread of a population coming from the north, but at a significantly earlier date than presently considered by archaeologists. Our data suggest that some of the mtDNA lineages found in southern Arabia have persisted in the region since the end of the Last Ice Age.