Naila, a young, beautiful Egyptian princess, dances incognito in the marketplace of Kemis, a royal city on the banks of the Nile River. Learning that her father has returned alone from a trip to the desert, Naila rushes back to the palace just in time to see him die. Told by Horadef, the lord counselor, that her father was killed by Herua, the leader of a band of escaped slaves, Naila demands revenge. She tells Herua that she plans to seek her father's killer by traveling the desert disguised as a peasant girl. Horadef then hires mercenaries to abduct the young queen so he can rule in her place. Once she is captured, she is branded a slave, but escapes into the desert as she is about to be sold to slave trader Maatet. She soon meets thieves Merab and Nebka, who take her with them to a nearby horse fair. After winning at the races, the three are captured by Maatet, only to be rescued from execution by Herua and his men. Naila is then taken to the slaves's secret village in the mountains, where the rebel leader professes his love to her. Learning that he is Herua, however, Naila puts aside her own romantic thoughts for those of revenge and asks that she be returned to the royal city so that she can act as Herua's spy. Back in Kemis, Naila reclaims her throne and sets a trap for Herua. The smitten Herua then arrives at their planned rendezvous and is quickly captured by Horadef's men. Though Herua proclaims his innocence in her father's death, the heartbroken Naila orders his execution. While he, too, is in love with Naila, Merab helps Herua escape from the executioner's ax by taking his place in the dungeon. When awakened the next morning, Merab claims to be the victim of black magic, having been whisked on a flying carpet from a harem into his prison cell. A bemused Naila orders his release, only to be taken captive herself by Horadef and his soldiers. While the two languish in their cells, Merab shows Naila the contents of Horadef's purse, which he had stolen. Recognizing her father's royal ring, she finally realizes that the lord counselor was her father's killer, not Herua. Later, Horadef tortures Merab on the rack until Naila agrees to tell him the location of Herua's hideout. She then leads Horadef and his troops down the narrow mountain passage to the slave city, knowing it is well protected. Warned by Merab of the impending invasion, Herua recognizes that Naila is leading Horadef's men to their doom, so he waits until she clears the pathway before unleashing an avalanche of boulders which protect his hideout. Horadef's remaining troops are defeated by the slave soldiers, while Horadef is killed by Merab. Returned to her rightful throne, Naila marries Herua, and Merab and Nebka go back to their lives as thieves.