I think I read this in the mid 90's. It was a fantasy novel set in the time of the Crusades. The protagonist was a half-djinn that lived among men. He'd been hired as a bodyguard to protect a family from assassins.
During the course of the story, the people he was protecting began a pilgrimage to Jerusalem. They were part of a larger caravan that included Knights Templar and Knights Hospitallers, with people wondering whether the hero would join either of those orders.
There was one scene where the hero approached a Christian shrine and wondering if he could approach as the other pilgrims in his caravan, or if he would burst into flames since he was not fully human (and djinn were considered a type of demon).
An assassin did strike at the family, and it turned out to be a female djinn. It was the first other djinn he'd ever met.
I think it may have been part of a trilogy, but I only read the first book.
Updated to add a couple of other things I remembered: The hero was left handed - during a meal, one of the Templars warned him that he needed to learn to eat right handed if he was going into Muslim controlled lands.
Also, the hero noticed that this particular Templar's beard was clean, unlike all the others that he'd met.
Minor details, probably, but they may help identify the book.