Two species are known from the Lower Oligocene Jebel Qatrani Formation of modern-day Egypt: C. ayeshae, and the more powerfully built C. robusta.

The genus is named for Cleopatra VII Philopator, the last Ptolemaic Queen of Egypt.

They were quite unspecialised at the anterior end of the mouth, with canines and incisors of a similar size, but the premolars and molars are very unusual.

Unlike the similar genus Ptolemaia, the premolars 3 and 4 do not possess parastyles.

For this reason, it has been hypothesised that it used them for cracking open shells or crushing some other resilient type of food.