When we discuss early Cinderellas, it is critical to recommend Fairytale in the Ancient World by Graham Anderson.
From my book, Cinderella Tales From Around the World:
Rhodopis, an Egyptian tale, is popularly labeled the earliest or first Cinderella story. The tale was first recorded by the Greek historian Strabo in the first century BC/AD and is generally considered to be loosely based upon a real person written about by Herodotus five hundred years before Strabo’s time. Rhodopis also appeared in Aelian’s Varia Historia (13.33) around the 2nd and 3rd centuries AD/CE.
I share three versions of the Rhodopis tale in the collection, beginning with translations of the earliest texts as well as two retellings of the story from the 19th century which take on greater literary flavor, demonstrating how larger tales are created from small pieces of earlier literature. They were also rewritten with a stronger Cinderella flavor to them although their ancient source materials are well-used, too. The tale was embraced during the golden age of fairy tales as a Cinderella tale and thus retold to fit those needs.
There is only one picture book version of this tale that I am aware of, The Egyptian Cinderella by Shirley Climo. The book description gives a sufficiently short and tidy summary of the tale:
Poor Rhodopis! She has nothing - no mother or father, and no friends. She is a slave, from the far-off country of Greece. Only the beautiful rose-red slippers her master gives her can make Rhodopis smile. So when a falcon swoops down and snatches one of the slippers away, Rhodipis is heartbroken. For how is she to know that the slipper will land in the lap of the great Pharoah himself? And who would ever guess that the Pharoah has promised to find the slipper's owner and make her queen of all Egypt?
All that said, there has to be a disclaimer, too, for many scholars reject this tale as a Cinderella tale since it doesn't meet enough of the elements or they have to be jiggled too much to accommodate a Cinderella label. Rhodopis isn't persecuted, per se, although arguing that she was a slave or a courtesan is sufficient for many to make her downtrodden and a victim. Others argue against a magical helper although some accept the eagle/falcon who drops her shoe near the pharoah to be sufficient for the role. The arguments expand much further than the scope of this short blog entry.
A shoe and royal marriage doesn't a Cinderella make, is the argument. Or does it? Anderson makes fitting arguments in his book and I recommend it for further reading about Rhodopis. As well as the original stories, of course.
And then the final decision is up to you. Because folklore is never easy.