Objectives: Genetic and archaeological research supports the theory that Arabia was the first region traversed bymodern humans as they left Africa and dispersed throughout Eurasia. However, the role of Arabia from the initialmigration out of Africa until more recent times is still unclear.Materials and Methods: We have generated 379 new hypervariable segment 1 (HVS-1) sequences from a rangeof geographic locations throughout Yemen. We compare these data to published HVS-1 sequences representing Arabiaand neighboring regions to build a unique dataset of 186 populations and 14,290 sequences.Results: We identify 4,563 haplotypes unevenly distributed across Arabia and neighboring regions. Arabia containshigher proportions of shared haplotypes than the regions with which it shares these haplotypes, suggestinghigh levels of migration through the region. Populations in Arabia show higher levels of population expansion thanthose in East Africa, but lower levels than the Near East, Middle East or India. Arabian populations also show veryhigh levels of genetic variation that overlaps with variation from most other regions.Conclusion: We take a population genetics approach to provide a comprehensive view of the relationships of Arabianand neighboring populations. We show that Arabian populations share closest links to the Near East and NorthAfrica, but have a more ancient origin with slower demographic growth and/or lower migration rates. Our conclusionsare supported by phylogenetic studies but also suggest that recent migrations have erased signals of earlierevents.