We here present the first detailed study of the specimen KNM-RU 18340 from Rusinga Island (Kenya), the only known complete early Miocene chameleon skull, using micro-CT. This specimen represents one of the oldest chameleon fossils ever recovered. For the first time, the skull bone internal surfaces, their sutures, and elements contained inside the rocky matrix are observed. Our morphological comparisons and phylogenetic analyses place this specimen confidently in the genus Calumma and a new species, Calumma benovskyi sp. nov., is erected for it. Since all species of this genus are endemic to Madagascar, this fossil uniquely demonstrates the existence of Calumma on continental Africa in the past. Our results challenge the long-held view that chameleons originated on Madagascar and dispersed over water to Africa, and provide a strong evidence of an African origin for some Malagasy lineages. The Oligocene-early Miocene dispersal to Madagascar, using oceanic currents that favoured eastward dispersal at that time, is a highly supported scenario matching the suggested dispersal of lemurs to this island. This is consistent with a previously suggested hypothesis based on molecular data.