The Old World fossil record of the family Camelidae is patchy, but a new partial cranium and some other remains of Camelus grattardi from the Mille-Logya Project area in the Afar, Ethiopia, greatly increase the fossil record of the genus in Africa. These new data – together with analysis of unpublished and recently published material from other sites, and reappraisal of poorly known taxa – allow for a comprehensive phylogenetic analysis showing that C. grattardi is the earliest (2.2–2.9 Ma) and most basal species of the genus. We also show that the lineages leading to the extant taxa C. dromedarius and C. bactrianus diverged much higher in the tree, suggesting a recent age for this divergence. A late divergence date between the extant species is consistent with the absence of any fossil forms that could be ancestral, or closely related, to any of the extant forms before the late Pleistocene, but stands in contrast to molecular estimates which place the divergence between the dromedary and the Bactrian camel between 8 and 4 million years ago.