His army had marched north to battle the Aksumites who had been fighting for control of Yemen for a hundred years. The Aksumites were only expelled from the region when the newly-Jewish king rallied Jews together from all over Arabia with pagan allies. The relationship between the Himyarite Kings and the polytheistic Arab tribes strengthened when, under the royal permission of Tubba' Abu Karib As'ad, Qusai ibn Kilab (400–480 CE) reconstructed the Ka'aba from a state of decay, and had the Arab al-Kahinan (Cohanim) build their houses around it. Qusai ibn Kilab was the great-great- grandfather of Shaiba ibn Hashim (Abdul-Mutallib). Shaiba ibn Hashim was fifth in the line of descent to Muhammad, and attained supreme power at Mecca. Qusai ibn Kilab is among the ancestors of Sahaba and the progenitor of the Banu Quraish. When Qusai came of age, a man from the tribe of Banu Khuza'a named Hulail (Hillel) was the trustee of the Kaaba, and the Na'sa (Nasi)—authorized to calculate the calendar. Qusai married his daughter and, according to Hulail's will, obtained Hulail's rights to the Ka'aba. Hulail, according to Arabian tradition was a member of the Banu Jurhum. Banu Jurhum was a sub-group of the Banu Qahtani from whom the Himyarites originally descend. Around 455 CE, the last Himyarite King is born, "Zur'ah Yusuf Ibn Tuban As'ad Abu Kaleb Dhu Nuwas" or Dhu Nuwas. He died in 510. His zeal for Judaism brought about his fall. Having heard of the persecutions of Jews by Byzantine emperors, Dhu Nuwas retaliated by putting to death some Byzantine merchants who were traveling on business through Himyara. He didn't simply kill them with hanging—he burned them in large pits—earning him the title "King of the burning pit". These killings destroyed the trade of Yemen with Europe and involved Dhu Nuwas in a war with the heathen King Aidug, whose commercial interests were injured by these killings. Dhu Nuwas was defeated, then he made war against the Christian city Najran in Yemen, which was a dependency of his kingdom.