We report on a new genus and species of herbivorous mammal, Pahelia mysteriosa, from the early Eocene Cambay Shale Formation, Tadkeshwar Lignite Mine, Gujarat, India. The new taxon, approximately the size of a small phenacodontid (e.g., Ectocion parvus), is represented by three mandibular fragments, the most complete of which documents nearly the entire symphysis and mandibular body plus P3-M3. Pahelia has incipiently selenolophodont molars with strong exodaenodonty, absent paraconids, weak but distinct entolophids, and prominent ectostylids. Molar size increases distally, but M3 does not develop a prominent third lobe. Premolars are simple, with prominent protoconids and short talonids but little development of other trigonid cusps. The mandibular symphysis is strongly fused, and there is an enlarged alveolus for an anterior tooth. The combination of features present in the new taxon does not closely match that of any known mammal, but there are some similarities to a diversity of ungulates from Africa, Asia, Europe, and North America. Preserved morphology is insufficient to confidently assess the affinities of the new taxon, but a link to Quettacyonidae, also endemic to the Indian subcontinent, is morphologically and biogeographically plausible. If this scenario is correct, it suggests that P. mysteriosa could be a part of the endemic mammalian fauna of India prior to its initial faunal contact with Asia.