Highlands, hydrographic systems and coastal areas have been hypothesised to form corridors across the hyperarid Sahara desert in North Africa, allowing dispersal and gene flow for non-xeric species. Here we aim to provide a genetic test for the trans-Saharan corridor model, and predict the location and stability of ecological-corridors, by combining phylogeography and palaeoclimatic modelling. The model was the Psammophis schokari (Schokari sand racer) group, fast-moving and widely distributed generalist colubrids occurring mostly in arid and semiarid scrublands. We combined dated phylogenies of mitochondrial and nuclear markers with palaeoclimatic modelling. For the phylogeographic analysis, we used 75 samples of P. schokari and P. aegyptius, and Bayesian and Maximum-Likelihood methods. For the ecological models, we used Maxent over the distribution of P. schokari and West African lineages. Models were projected to past conditions (mid Holocene, Last Glacial Maximum and Last Inter-Glacial) to infer climatic stable areas. Climatic stability was predicted to be mostly restricted to coastal areas and not spatially continuous. A putative temporary trans-Saharan corridor was identified in Eastern Sahara, with a more stable one along the Atlantic coast. Six parapatric lineages were identified within P. schokari, four occurring in North Africa. These likely diverged during the Pliocene. The Tamanraset River might have been a vicariant agent. African lineages may have experienced further subsequent diversification during the late Pleistocene. The main P. schokari refugia were probably located along the northern margins of the Sahara, allowing its North-to-South colonization. Trans-Saharan corridors seem to have played a role in P. schokari biogeography, allowing colonization of central Saharan mountains and Sahel. Some might have worked as refugia, and even the most stable corridors may have sections working as filters, depending on each climatic phase. We expect the use of trans-Saharan corridors to decrease for more mesic species or with less dispersal capabilities.