Potwarmus is recorded for the first time in Saudi Arabia. The material comes from the Middle Miocene of the Hofuf Formation at Al-Jadidah. This species, Potwarmus flynni sp. nov., is described and compared with all species currently placed in the genera Potwarmus, Dakkamys, Paradakkamys, Vallaris, and some species of ?Myocricetodon? (i.e. the so-called ?primitive dendromurids?) as well as with two of the most primitive definitive murines (namely Antemus chinjiensis and Progonomys debruijni). Potwarmus flynni sp. nov. differs from the above-mentioned species in having the anterior part of the m1 strongly reduced. A cladistic analysis provides evidence that this new Arabian taxon is close to Potwarmus primitivus and Potwarmus sp. nov. from Jebel Zelten (Libya), and also that this genus is unlikely to be the sister taxon to Antemus.