We tested the camouflage hypothesis, or the linkage between animal (Saharan rodent) and habitat coloration, on the largest geographical scale yet conducted. We aimed to determine whether phenotypic variation is explained by micro-habitat variation and/or genetic polymorphism to determine 1) the strength of linkage between fur color and local substrate color, and 2) the divergence in fur coloration between two genetic clades, representing cryptic species, throughout the complete range of the African desert jerboas (Jaculus jaculus). We used a combination of museum and field-collected specimens, remote sensing tools, satellite and digital photography and molecular genetic and phylogenetic methods to investigate the above hypotheses. Along with showing that the two divergent genetic clades of jerboas occur sympatrically throughout their African distribution, we showed significant covariation between dorsal fur coloration of the animals and the color of their habitat. We also described significant phenotypic divergence in fur color, consistent with genetic divergence between the sympatric clades. The linkage between environment and phenotype supports the idea that the selection promoting cryptic coloration is persistent in contemporary populations of jerboas, however the phenotypic divergence indicates that it has different strengths (or optima) in the two clades. The mosaic distribution of micro-habitats occupied by geographically sympatric clades suggests that it may influence both ecological and evolutionary dynamics between these two cryptic species.