During the First Crusade, Khalid was a war-leader of the Muslims, earning a bloody reputation from the crusaders and committing many atrocities. He was Embraced by a Byzantine Nosferatu who believed the safest way of driving Islamic influence out of Palestine was by corrupting their leaders. Khalid's first reaction to his Embrace was a violent Frenzy that claimed the life of many of his followers.
He was saved from the rays of the sun by a Jewish hermit, who taught him about his state and the kabbalah. During his travels to various holy sites of Islam, he learned of Golconda and committed himself to this state. For six centuries, he searched for this state, but whenever he seemed close to it, his Beast drove him away.
Khalid came to Chicago in 1871, searching for one of the Inconnu. Despite his original support for Lodin's princedom, he soon came to resent him and voted to overthrow him. During a flood, he was driven from his sewer domain and when the Lupines invaded Chicago, Khalid was one of the few Kindred who managed to organize a defense, killing many Lupines with his own hands.
During his long stay in the city, he has learned of the machinations of both Helena and Menele and is intrigued by the sheer dimensions of their feud. Recently, he has come to consider leaving Chicago in his search for Golconda, but is aware of the severe political repercussions this could have on the city.