This is the first genetic anthropology study on Arabs in MENA (Middle East and North Africa) region. The present meta-analysis included 100 populations from 36 Arab and non-Arab communities, comprising 16,006 individuals, and evaluates the genetic profile of Arabs using HLA class I (A, B) and class II (DRB1, DQB1) genes. A total of 56 Arab populations comprising 10,283 individuals were selected from several databases, and were compared with 44 Mediterranean, Asian, and sub-Saharan populations. The most frequent alleles in Arabs are A*01, A*02, B*35, B*51, DRB1*03:01, DRB1*07:01, DQB1*02:01, and DQB1*03:01, while DRB1*03:01-DQB1*02:01 and DRB1*07:01-DQB1*02:02 are the most frequent class II haplotypes. Dendrograms, correspondence analyses, genetic distances, and haplotype analysis indicate that Arabs could be stratified into four groups. The first consists of North Africans (Algerians, Tunisians, Moroccans, and Libyans), and the first Arabian Peninsula cluster (Saudis, Kuwaitis, and Yemenis), who appear to be related to Western Mediterraneans, including Iberians; this might be explained for a massive migration into these areas when Sahara underwent a relatively rapid desiccation, starting about 10,000 years BC. The second includes Levantine Arabs (Palestinians, Jordanians, Lebanese, and Syrians), along with Iraqi and Egyptians, who are related to Eastern Mediterraneans. The third comprises Sudanese and Comorians, who tend to cluster with Sub-Saharans. The fourth comprises the second Arabian Peninsula cluster, made up of Omanis, Emiratis, and Bahrainis. It is noteworthy that the two large minorities (Berbers and Kurds) are indigenous (autochthonous), and are not genetically different from “host” and neighboring populations. In conclusion, this study confirmed high genetic heterogeneity among present-day Arabs, and especially those of the Arabian Peninsula.