Obtain Quest: Interact with billboard near entrance to Desert town
Prerequisites (As Far As I’m Aware): Own the Sandy Shack
Guide
Go to the noticeboard at the northern edge of the desert town. Interact with the left side of the board and you'll get a message about a wanted poster for a cannibal. Go east of the town, and in the northern half of the next zone, you'll find a guard with a dead body. Talk to the guard, who'll explain the body is another victim of the cannibal, and asks you to track him.
Follow the footprints in sand further east, and you'll eventually come to a small set of hills leading up into the nomad camp. Head to the eastern edge of the camp, near the purple-haired woman (Viper Nazir) and then start going down the slope south of her. She'll talk to you, then run off towards a cliff north-east of the zone, and open a cave. Follow her in and go through the cave until you reach a set of five statues. Nazir will get blocked by a barrier and keep attacking it. You need to interact with the statues to get them all green. When you interact with one, it switches it's own colour and the two either side of it.
For those who want to figure it out yourself, ignore this bit. For those who want a quick solution, follow this sequence (numbers for statues based on attached image).
1
3
2
5
4
Once all the lights are green, the barrier goes, and you and Nazir can move on. When you reach the gap with the bridge on the other side, talk to Nazir, and she'll jump over and move the bridge after a small conversation, wherein you can agree to take 30% or go 50/50. No idea why you'd choose 30, and I've not tried it, so just go 50, lol. It likely doesn't make a difference though.
Once Nazir joins your party as a mercenary (suggested you move her to battle party before continuing if it isn't already full), carry on until you reach the cannibal. Once he finishes talking it starts a battle with him. It should be a very easy fight, and once he's down, after a short cutscene you'll be taken back to the town palace. After another cutscene, in which the guards refuse to pay you, Nazir will officially join you (as a reminder, she is not a slave, so cannot be used as a whore or similar at brothels).
*Text taken from the old Tomb Raiding quest page