Myotragus palomboi n.sp. (Artiodactyla, Caprinae) is described from the Early Pliocene of Mallorca (Balearic Islands, western Mediterranean). This species is the earliest representative of the Myotragus lineage known to date in the Balearic Islands. A metatarsal, and several teeth and postcranial remains were found in a karstic deposit located on the east coast of the island, near Caló den Rafelino (Manacor), together with remains of Hypolagus, two rodent species, an insectivore and several reptiles. The metatarsal and phalanges of the new bovid are short and robust and display a combination of characters only observed in Myotragus. The presence of a larger p2, a metatarsal robustness index lower than in M. pepgonellae (the earliest known species to date), together with the morphology of the incisors, all suggest that M. palomboi should be considered as the ancestor of M. pepgonellae. Short metapodials and the reduction of p2 displayed by M. palomboi could be linked to a first stage of evolution in insular conditions. The arrival of this bovid to the island of Mallorca probably took place during the Mediterranean Messinian Salinity Crisis (Late Miocene, 5.6–5.32 Ma ago). Although the relationship of the new taxon to other fossil caprines cannot be definitively established, it could be phylogenetically close to the Late Miocene European species Aragoral mudejar and Norbertia hellenica.