Recent palaeontological field campaigns in the westernmost part of the Sahara (Dakhla region, Morocco) have resulted in the discovery of a mammal assemblage including anomaluroid rodents. This new fauna comes from the uppermost part of the Samlat Formation, which contains estuarine deposits dating from the earliest Oligocene. The anomaluroid record from Dakhla (C2) comprises at least five sympatric taxa distributed among four different groups (Anomaluridae, Zenkerellinae, Nonanomaluridae and ?Zegdoumyidae), and includes two new species attributed to Paranomalurus Lavocat, 1973 (P. riodeoroensis Marivaux sp. nov.; Anomaluridae) and Nonanomalurus Pickford et al., 2013 (N. parvus Marivaux sp. nov.; Nonanomaluridae), genera well known from the early Miocene of Sub-Saharan Africa. Three other new anomaluroid taxa - a diminutive anomalurid, Argouburus minutus Marivaux gen. et sp. nov., a zenkerelline-like anomaluroid, Oromys zenkerellinopsis Marivaux gen. et sp. nov., and a ?zegdoumyid, Dakhlamys ultimus Marivaux gen. et sp. nov. - are also documented but remain poorly sampled. The presence in Dakhla (C2) of primitive representatives of two early Miocene anomaluroid genera (Paranomalurus and Nonanomalurus) and a possible zenkerelline extends back to the earliest Oligocene the stratigraphical range of these lineages. This exceptional record from Dakhla demonstrates that anomaluroids were diverse near the global cooling event recorded at the Eocene/Oligocene transition, thereby indicating that coastal forests situated in the tropical south-western margin of North Africa were locally less affected by the climatic changes. The occurrence of Paranomalurus and Nonanomalurus in the earliest Oligocene reveals the surprisingly long-lived evolutionary pattern of these two genera, which otherwise remained highly conservative through time, especially regarding dental patterns. Considering the palaeontological data so far available and our proposed phylogenetic context including a comprehensive taxonomic sampling for anomaluroids, it appears that the divergences of extant lineages (Anomalurus, Idiurus and Zenkerella) were very ancient, and probably can be traced back to the Eocene. Based on our phylogenetic results, some systematic and macroevolutionary implications related to the nomaluroidea are discussed, with a special emphasis on the Zenkerella lineage, which is regarded here as possibly outside the Anomaluridae.