Providence continues on its way and Cook gives the new crew instructions on how to haul up the sail. Sinbad finally helps them out and they get the sail up, but they improperly tie it off and a disgusted Cook yanks on the note, causing the sail to fall back down again. Gunnar lifts the spar for them and Cook puts them back to work.
Later, the ship arrives at a bay and Anwar tries to find their position while Cook serves a meal. Nala starts to give orders, saying that they need to find a port so that they can go their separate ways, and Sinbad questions her assuming command. Rina and Gunnar agree with Nala that there is nothing to hold them together and they should go their separate ways, while Anwar and Sinbad are eager to taste their newfound freedom. Cook tells them that before they go anywhere, they have to go to the nearby island to get fresh water and supplies. According to his maps, Anwar believes that they're at the island of Sind, and that its population was wiped out years ago. As they talk about going shore, Sinbad nervously fingers his cursed pendant. They are all unaware that grey-faced child is watching them from the island cliffs.
In Basra, the Emir shows Akbari and Taryn his model of the modern city that he plans to build as a monument to science and learning. Akbari persists in reminding his brother that Sinbad has escaped, and the Emir says that he will have his guards search the city to find anyone who knows where Sinbad has fled. Taryn says that she should use magic but the Emir takes offense, reminding her that he has banned the dark arts from his city. When he orders a guard to remove her, Taryn snarls and walks out on her own. As Akbari prepares to leave, the Emir warns him that the dark arts can eat at a man's soul, and that he will do everything humanly possible to bring Sinbad back.
Outside, Akbari tells Taryn to use her magic to find Sinbad. She warns that the Emir is right to be cautious and that casting such a spell can be dangerous. However, Akbari insists and walks away as Taryn secretly smiles in satisfaction.
That night, everyone on Providence dozes off. Sinbad is wakened by the sound of someone boarding the ship and goes to investigate. Meanwhile, Nala wakes up and finds a feral child in her bedroom. She draws her father's dagger and threatens the child, who cowers in fear. Nala lowers her knife and assures the boy that she mean him no harm, but he takes out his own knife and captures her. On the ship, Sinbad finds another of the feral children. When he tries to capture her, another intruder knocks him unconscious. When he wakes up the next morning, Sinbad discovers that everyone but Cook has been captured by the intruders. The savages take the crew and the supplies to the island aboard rafts while two of their number stand guard. They hear someone laughing below and investigate. Cook is making a meal and invites them to join him.
The Providence crew are taken to a large abandoned city decorated with skeletons and pyramids. When they are brought ashore, Sinbad hesitates again and touches his pendant, and Rina notices. They are taken onto land and escorted to the town square where they are placed in a circle of stones. The savages circle around them but then bow down as a woman gives out an unearthly shriek. Sinbad and the others look up and see a beautiful young woman, Razia, her face covered in henna tattoos. The natives bow before her and she tells them to bring Sinbad and Gunnar forward. Razia contemplates the two men and then tells her people, led by Khalid, to bring Gunnar to her quarters. Sinbad trips his fellow crewman and offers himself in the northerner's place. He gives her name assures Razia that she'll never forget him, and she takes him up on his offer. Razia then drops loafs of bread down a wooden chute to feed her people and assures them that they will have fresh meat that night as a reward for capturing the ship.
Onboard the ship, Cook feeds the two savages using hidden emergency supplies that the others didn't find.
Sinbad is escorted to Razia's quarters within a huge stone building. Before she arrives, he grabs a carving fork and spots an archway leading outside. However, he finds that it leads to a sheer drop to the sea below. As he retreats, Sinbad spots a chain and tries to pull it free so he can use it as a makeshift rope. When he pulls, the enormous roc that it is fastened to emerges from its stall. Sinbad evades it and jumps down out of its reach as Razia comes in. As she undresses, she assures Sinbad that it can't break the chains and that it once flew over the city when it was a place of knowledge. Razia wonders why Sinbad offered himself and accuses him of plotting to overpower her. Wielding her staff of office, Razia reveals a hidden blade and slashes at Sinbad. He uses his acrobatic skills to avoid her until he can grab the staff and stop her.
Gunnar, Anwar, Nala, and Rina are placed in cages and left alone. As Rina tries to pick the lock, Anwar insists that Sinbad only abandoned them because he has a plan to free them all. Gunnar and Rina don't believe it and Gunnar warns that they are the fresh meat that Razia promised her people.
As Razia sharpens her staff blade, Sinbad insists that he felt a spark between them and that he knows that she did as well. She explains that she chose him because she can't reveal herself as anything less than untouchable to the men of her tribe, the Water-Thieves. Sinbad says that he understands, claiming to be a leader, but Razia tells him that he may be a thief and a gambler but he's no leader because he abandoned his crew.
One of the savages, Malik, returns to the cells and knocks Rina back from the lock. He tells Gunnar that he will fight to the death against Anwar that night, but the northerner refuses. Rina offers to fight the doctor instead, saying that it's a fairer match, and Malik agrees. He warns Gunnar that they have something else in mind for him if he won't fight and leaves. Once they're alone, Rina angrily demands to know why Gunnar won't fight but he ignores her question.
Sinbad joins Razia in bed and starts to undress, and then threatens her with the serving fork he stole earlier. She has Nala's dagger and holds it to his heart, confident that he won't risk his life because he cares more about himself then his friends. Sinbad tosses the fork away and she thrusts the dagger into her bedpost and then advances on Sinbad. She notices the pendant and he explains about Safia's curse. Razia tells him that he and her roc are similar in that they both belong to her and that they both are in chains. She concentrates for a moment and the henna tattoos on her face disappear, revealing her true beauty. Sinbad is taken aback and Razia explains that her face is what she once was, but the tattoos serve as the mask of leadership for her. She then kisses Sinbad and throws him down on the bed.
In Basra, Sinbad's friend Tazeem finds Zahira in the market. Safia grabs him and holds a knife to his throat until she realizes who he is. Tazeem warns the old woman that the guards are seeking anyone who knows Sinbad, and offers to get Zahira out of the city on the caravan. Safia agrees but insists on staying in the city for a while longer.
The savages on Providence pass out thanks to Cook's drugged food.
Sinbad wakes up later and finds Razia with the tattoos back on her face. When he invites her back to bed, she throws him off and tells him that she has mouths to feed.
The savages take Gunnar out of his cage and haul him away. Once they're alone, Rina, Anwar, and Nala try to break out of their cage without success.
As he waits in Razia's quarters, Sinbad takes some water to the roc, which hesitantly drinks. Khalid comes in and informs Sinbad that the skulls that decorate the chamber belong to Razia's former lovers, and that Razia will cut Sinbad's throat just as readily. Sinbad asks if he's jealous and Khalid explains that he is Razia's son, and that she killed his father just like all the rest. She shows him no favor nor does he want any, for Razia loves all of the tribe equally, putting nothing before the needs of her people. Sinbad wonders if the Water-Thieves know that Khalid is their leader's son and he says that it would make no difference because she loves them all as one.
That night, the savages gather in the town square and Razia comes forth to lead them. She reminds them of how they were nothing until she organized them and made them a single people. As they cheer her, Gunnar is brought in, dressed as serving girl, and forced to give them food. A disgusted Khalid tells the northerner that he could have died as a man if he had fought as one.
Sinbad tries to offer meat to the roc but it snaps at him, forcing him back.
Nala, Anwar, and Rina are escorted into the town square. Khalid tells Anwar and Rina that they must fight to the death and the winner will be allowed to live... a little longer.
When the roc refuses to move, Sinbad snaps at it, saying that it may know freedom but that he will die come sunrise without knowing freedom. Apparently understanding, the roc gestures for Sinbad to pass. He runs to the ledge and then starts climbing up the cliff.
In the stone circle, Rina savagely attacks Anwar, who refuses to fight back because she's a woman. As she starts throttling him, Sinbad arrives. He looks longingly at the ship and considers escaping, but then goes to help his crew. Anwar sees him and tries to tell Rina, but she's consumed with bloodlust. Sinbad drops more fruit down the chute, distracting the Water-Thieves. Gunnar attacks one of the savages that was taunting him while Rina attacks another. Sinbad fights Khalid and manages to disarm him, while Nala kicks her guard when he tries to kill Rina. Gunnar is consumed by bloodlust but Anwar manages to stop him from killing his opponent.
Sinbad holds Khalid's sword to the man's neck and holds him as a hostage, demanding that Razia let them go in peace. She doesn't believe that Sinbad is strong enough to kill a man, and Sinbad responds by telling the Water-Thieves that Khalid is Razia's son. Malik questions his queen but she insists that it doesn't matter because she cares for all of them equally. Seeing his chance, Malik dares her to kill Khalid and prove what she says. Razia steps forward, her knife-staff ready, but is finally unable to do it. She turns away, the tattoos disappearing from her face as she breaks into tears. Malik grabs a spear and kills Khalid himself, and a crying Razia runs to her son's corpse. Sinbad grabs the keys to the roc's chains from Khalid's belt and runs off, while his four crew members head for the beach. Malik takes command and leads his people after the Providence crew.
Sinbad hides until the Water-Thieves run past and then runs past Razia to her quarters. With every step his cursed pendant tightens further as the sun rises and his single day on land runs out. Sinbad grabs Nala's dagger from the bedpost and then frees the roc. When it hesitates, Sinbad drives it out onto the ledge until it falls off and then soars off into the sky, free. Razia arrives, her leadership tattoos back in place, and prepares to kill Sinbad. She forces him back to the ledge and he fights back until the pendant becomes too tight. Smiling in triumph, Razia insists that she gave her people order and warns that they will tear themselves apart without her. Gasping for breath, Sinbad tells her that she is the one who needs her people, and that they will love her with or without her mask. Angry, Razia kicks him over the edge and Sinbad falls to his death... until the roc arrives and carries him to safety. As Razia stares in shock, Malik comes in behind her and says that he is there to kill her as well as her son. She turns and, staff raised, dares him to try.
Gunnar and the others steal a canoe and row out to Providence with the savages in hot pursuit. Cook helps them on board but warns that the ship will not sail without Sinbad. The roc arrives and drops Sinbad into the water, and he swims to the ship. As he climbs up, the roc drives off the savages and then flaps its wings, propelling the ship out of the bay. As the crew celebrates, Gunnar wonders what happened to the guards and Cook chuckles. Meanwhile, Nala turns to Sinbad and asks what his orders are. He gives her the dagger and then says that they will seek out freedom.