O wyborze tematu i tytułowej postaci zdecydowała zapewne popularność ostatniej królowej Egiptu oraz jej dramatu miłości i władzy, od wieków utrzymująca się w sztuce i literaturze europejskiej. Fabułę utworu Haggard oparł zasadniczo na faktach podanych przez historiografię antyczną. Do pisania przygotowywał się przyswajając sobie dostępną wówczas wiedzę o wierzeniach i obyczajach staroegipskich, o czym pośrednio świadczą jego przypisy objaśniające.
Pełny, rzadko uwzględniany tytuł powieści brzmi: Cleopatra – being an account of the fall and vengeance of Harmachis, the Royal Egyptian, as set forth by his own hand („Kleopatra, to jest relacja o upadku i zemście Harmachisa, Egipcjanina krwi królewskiej, własnoręcznie przez niego przedstawiona”). W formie kieszonkowej (wówczas nowość) książka ukazała się w 1889 r. w londyńskim wydawnictwie Longmans, Green & Co. – niemal równolegle z popularną powieścią historyczno-przygodową Kot z Bubastis („The Cat of Bubastes”) George’a A. Henty'ego, również osadzoną w tematyce staroegipskiej. W tym samym roku opublikowano też przekład niemiecki (w Lipsku, w wydawnictwie B. Tauchnitza).