In 1987, nine groups of graffiti written in Safaitic were published from Pompeii's theatre corridor (VIII.7.20). Safaitic, a south Semitic script used to record a dialect of Old Arabic, had never previously been documented in the West, and the appearance of these inscriptions at Pompeii since their publication has largely remained a mystery. I argue that Pompeii's Safaitic graffiti were inscribed by nomads from the Ḥarrah who had been incorporated into the Roman army, and who marched into Italy with Legio III Gallica during its campaign to install Vespasian as emperor.