The Lophiodontidae are a European Eocene perissodactyl family that includes the genera Lophiaspis, Lophiodon and Paralophiodon. Despite their high specific diversity, their abundance and their dominance over Eocene large herbivores, the origin of this group still remains unclear. The La Borie locality (early Eocene, MP8-9), near Issel, Southern France, has yielded a new and well preserved skull of a new early lophiodontid. Building on this new specimen, a new phylogenetic hypothesis is proposed for Lophiodontidae, based on a cladistic analysis of dental, cranial and mandibular characters. The specimen displays a unique morphology that leads us to propose the new genus and species Eolophiodon laboriense. This monospecific genus is the sister group of the clade gathering Lophiodon and Paralophiodon. From the obtained phylogeny, it is proposed that the well-known group of derived lophiodonts might have arisen in Southern Europe soon after the origin of the family, and most probably from a Lophiaspis-like stock.