We generated an extensive morphological and multilocus molecular dataset to investigate the taxonomy of Acanthodactylus erythrurus, a widespread species across the Mediterranean and semiarid habitats of the Iberian Peninsula and the Maghreb. Our integrated analyses revealed the existence of at least five basal lineages: (i) an Ibero-Moroccan clade widespread across Morocco and the Iberian Peninsula, from sea-level up to a maximal known altitude of 1,930 m, (ii) an Algero-Tunisian clade, distributed in coastal and inland areas of eastern Algeria and Tunisia, (iii) a Central Algerian clade, formed by two inland populations located in central Algeria (1,000–1,500 m a.s.l.), (iv) a western High Atlas clade including two montane populations from Jbel Siroua and Tizi n’Tichka (at 2,320 m and 2,176 m a.s.l., respectively) and (v) an eastern High Atlas clade, including at least two montane populations from Isli and Tislit (both localities around 2,275 m a.s.l.). An integrated species delimitation approach combining molecular and multivariate morphological analyses demonstrated complete reproductive isolation and hence speciation between the Ibero-Moroccan clade and the eastern High Atlas clade in their contact zone. The divergence between all five clades is broadly similar, supporting the existence of at least five species in the Acanthodactylus erythrurus complex. In the present work we describe the two well-differentiated endemic species from the Moroccan Atlas for which no name is available: Acanthodactylus lacrymae sp. nov. from Isli and Tislit and A. montanus sp. nov. from Jbel Siroua and Tizi n’Tichka. Further work will be needed to fully resolve the taxonomy of this species complex.