We have used mitochondrial 12S rRNA, 16S rRNA and nuclear beta-fibrinogen (intron 7) sequences to investigate the phylogenetic and phylogeographic relationships between Acanthodactylus erythrurus group species (except for A. boueti). The phylogenetic analyses of the Acanthodactylus genus did not cluster A. guineensis and A. savignyi with the remaining species of the group (A. blanci, A. lineomaculatus and A. erythrurus). Within the A. erythrurus group, the results of the mitochondrial DNA (mtDNA) and nuclear DNA (nDNA) showed a complex phylogeny with geographic structure, but it was not congruent with the present taxonomy. Some taxonomic units, such as A. blanci, A. lineomaculatus, A. e. atlanticus and A. e. belli did not form monophyletic genetic units. The application of a molecular clock suggested that the uplift of the Atlas Mountains in the mid-late Miocene and the reopening of the Strait of Gibraltar could be major biogeographic events responsible for the genetic differentiation in the group. Additionally, diverse micro-evolutionary patterns due to the recent contraction/expansion phases of the habitats in North Africa associated with the high dispersal capabilities of these lizards could be related to the complex phylogenetic patterns observed.