Recent extensive field prospecting conducted in the Upper Miocene of Lebanon resulted in the discovery of several new fossiliferous localities. One of these, situated in the Zahleh area (Bekaa Valley, central Lebanon) has yielded a particularly diverse vertebrate fauna. Micromammals constitute an important part of this assemblage because not only do they represent the first Neogene rodents and insectivores from Lebanon, but they are also the only ones from the early Late Miocene of the Arabian Peninsula and circumambient areas. Analyses of the murines from Zahleh reveal that they belong to a small-sized early Progonomys, which cannot be assigned to any of the species of the genus hitherto described. They are, thereby, shown to represent a new species: Progonomys manolo. Morphometric analyses of the outline of the first upper molars of this species suggest a generalist and omnivorous diet. This record sheds new light onto a major phenomenon in the evolutionary history of rodents, which is the earliest dispersal of mice. It suggests that the arrival of murines in Africa got under way through the Levant rather than via southern Europe and was monitored by the ecological requirements of Progonomys.