I was thinking that he could be a survivor of a caravan that was attacked by the Brotherhood of the True Flame. He manages to kill a few while the rest of the caravan is raided and stolen. He's left to die (not worth the trouble to kill him) in the sands. He doesn't. He makes it back to the city half dead and full of vengeance. He's healed up just as he hears about another expedition heading back out and wants to pay his respects to the Brotherhood again.
Would that work? I'd probably flesh out more of the deep background to give QL more ways to cause misery later, but that might be the immediate hook.
That works fine. Before, [MENTION=6855130]Jago[/MENTION] was playing "Kaniel", a half-orc barbarian (path of the dervish), who bears cosmetic similarities with your character.
While the PCs currently suspect the Brotherhood's involvement, there's a lot of unknowns. The OP provides a pretty good description. But I'd
strongly STRONGLY encourage the 3 players who've been around longest to bring new folks up to speed, especially when it comes to your investigation in the city (i.e. questioning Jina the Bold & Suelasta the Magnificent & the brothers).
Each of the current PCs was sent by a different NPC/organization. Interestingly, the Grand Caliph (think: Emperor) didn't send any of the 3 current PCs...so that's an open hook for any new characters...
Vizier Akilah ( [MENTION=6814006]Thateous[/MENTION] ) was asked by her father the Sheikh of Tajar, City of Trade, to investigate what is causing the caravan raids and stop them.
Ankabut ( [MENTION=4936]Shayuri[/MENTION] ), disguised as the acolyte "Amina", was sent by the Soft Whisper holy slayers to eliminate several Brotherhood members believed to be operating in the region.
Salahuddin ( [MENTION=6803188]VLAD the Destroyer[/MENTION] ) was sent by the Great Caliph of the Djinn...though I'm blanking on the specifics. Maybe you remember more clearly VLAD?