In the absence of a comprehensive fossil record, the origin and early evolution of Malagasy lemurs have been subject to much uncertainty. We report here the discovery of a strepsirrhine fossil with strong cheirogaleid lemur affinities, Bugtilemur mathesoni gen. et sp. nov., from early Oligocene deposits of the Bugti Hills (Balochistan, Pakistan). Bugtilemur represents the earliest record of Lemuriformes, which hence appear to have already diversified outside of Madagascar at least 30 million years ago. This fossil clearly enhances the critical role of the Indian subcontinent in the early diversification of lemurs and constrains paleobiogeographic models of strepsirrhine lemur evolution.