Mesalina are small diurnal lacertid lizards inhabiting arid areas from North Africa to northwestern India. Previous phylogenetic studies have shown the existence of several species complexes within the genus, some of them with high levels of undiscovered diversity. In the present study, we carry out an integrative systematic revision of the Mesalina guttulata species complex using both molecular and morphological data from across its entire distribution range in North Africa, the Middle East and Arabia. The results of the genetic analyses indicate that M. guttulata and M. bahaeldini are two allopatric sister taxa separated by the Suez Canal and that the species complex includes a further three unnamed deep phylogenetic lineages, two of them restricted to southern and southwestern Arabia and described herein as Mesalina austroarabica sp. nov. and Mesalina arnoldi sp. nov., respectively. As a result of the lack of enough material, the third deep lineage, distributed across Kuwait, Saudi Arabia and Jordan, is provisionally left undescribed. The two newly described species are characterized by their size, scale counts and tail coloration, as well as differences at the three mitochondrial and one nuclear gene analyzed in the present study.