Plesiadapiforms represent the first radiation of Primates, appearing near the Cretaceous-Paleogene boundary. Eleven families of plesiadapiforms are recognized, including the Paromomyidae. Four species of paromomyids from the early Eocene have been reported from Europe: Arcius fuscus, Arcius lapparenti, and Arcius rougieri from France, and Arcius zbyszewskii from Portugal. Other Arcius specimens from the early Eocene are known from Masia de l’Hereuet (Spain), Abbey Wood (England), and Sotteville-sur-Mer (Normandy, France). A cladistic analysis of the European paromomyids has never previously been published. A total of 53 dental characters were analyzed for the four Arcius species and the specimens from Spain, England, and Normandy. The results of a parsimony analysis using TNT agree with previous conceptions of A. zbyszewskii as the most primitive member of the genus. Also consistent with existing hypotheses, Arcius rougieri is positioned as the sister taxon of A. fuscus and A. lapparenti, and the results suggest that the fossil from Normandy is A. zbyszewskii. However, the English fossil pertains to a primitive lineage, rather than grouping with A. lapparenti as had been suggested; as such it is recognized here as a distinct species (Arcius hookeri). The Spanish fossils cluster together with the French species, but do not show the previously proposed special relationship with A. lapparenti, and are sufficiently distinct to be placed in a new species (Arcius ilerdensis). Arcius is recovered as monophyletic, which is consistent with a single migration event from North America to Europe around the earliest Eocene though the Greenland land bridge.