In 1967 G.G. Simpson described three partial mandibles from early Miocene deposits in Kenya that he interpreted as belonging to a new strepsirrhine primate, Propotto. This interpretation was quickly challenged, with the assertion that Propotto was not a primate, but rather a pteropodid fruit bat. The latter interpretation has not been questioned for almost half a century. Here we re-evaluate the affinities of Propotto, drawing upon diverse lines of evidence to establish that this strange mammal is a strepsirrhine primate as originally suggested by Simpson. Moreover, our phylogenetic analyses support the recognition of Propotto, together with late Eocene Plesiopithecus from Egypt, as African stem chiromyiform lemurs that are exclusively related to the extant aye-aye (Daubentonia) from Madagascar. Our results challenge the long-held view that all lemurs are descended from a single ancient colonization of Madagascar, and present an intriguing alternative scenario in which two lemur lineages dispersed from Africa to Madagascar independently, possibly during the later Cenozoic.