Kelba quadeemae, a fossil mammal from the Early Miocene of East Africa, was originally named on the basis of three isolated upper molars. Kelba has previously been interpreted as a creodont, a pantolestid, an insectivoran, and a hemigaline viverrid. The true affinities of this taxon have remained unclear because of the limited material and its unique morphology relative to other Miocene African mammals. New material of Kelba from several East African Miocene localities, most notably a skull from the Early Miocene locality of Songhor in Western Kenya, permits analysis of the affinities of Kelba and documents the lower dentition of this taxon. Morphological comparison of this new material clearly demonstrates that Kelba is a member of the order Ptolemaiida, a poorly understood group whose fossil record was previously restricted to the Oligocene Fayum deposits of northern Egypt. Phylogenetic analysis supports the monophyly of the Ptolemaiida, including Kelba, and recovers two monophyletic clades within the order. We provide new family names for these groups and an emended diagnosis for the order. The discovery of ptolemaiidans from the Miocene of East Africa is significant because it extends the known temporal range of the order by >10 million years and the geographic range by >3,200 km. Although the higher-level affinities of the Ptolemaiida remain obscure, their unique morphology and distribution through a larger area of Africa (and exclusively Africa) lend support to the idea that Ptolemaiida may have an ancient African origin.