A phylogeographic study was conducted on the Nile grass rat, Arvicanthis niloticus, a rodent species that is tightly associated with open grasslands from the Sudano-Sahelian regions. Using one mitochondrial (cytochrome b) and one nuclear (intron 7 of Beta Fibrinogen) gene, robust patterns were retrieved that clearly show that (i) the species originated in East Africa concomitantly with expanding grasslands some 2 Ma, and (ii) four parapatric and genetically well-defined lineages differentiated essentially from East to West following Pleistocene bioclimatic cycles. This strongly points towards allopatric genetic divergence within savannah refuges during humid episodes, then dispersal during arid ones; secondary contact zones would have then stabilized around geographic barriers, namely, Niger River and Lake Chad basins. Our results pertinently add to those obtained for several other African rodent as well as non-rodent species that inhabit forests, humid zones, savannahs and deserts, all studies that now allow one to depict a more comprehensive picture of the Pleistocene history of the continent south of the Sahara. In particular, although their precise location remains to be determined, at least three Pleistocene refuges are identified within the West and Central African savannah biome.