At what time Christianity was first introduced into Arabia Felix is uncertain. This part of Arabia was in a measure shut off from the world of the Romans until the expedition of Ælius Gallus. Before the coming of Christianity the Yemenites were either idolaters or Sabeans. The large numbers of Jews in Yemen was an additional obstacle to the early spread of the faith as they were always bitterly hostile to the missionaries. The legend that St. Bartholomew preached in Yemen on his way to India need not be considered; nor the more probable one of Frumentius and his success as first bishop to Himyar. In the reign of Constantius, Theophilus, the deacon of Nicomedia, a zealous Arian, was sent by the emperor to attend a magnificent embassy to the court of Himyar and is said to have prevailed on the Arabian king to embrace Christianity. He built three churches in different parts of Yemen, at Zaphar, Aden and Sana, as well as at Hormuz in the Persian Gulf. No less than four bishoprics were established and the tribes of Rabia Ghassan, and Kodaa were won to the faith. Ibn Khalikan, the Arabian historian, enumerates as Christian tribes, the Bahrah, Tanoukh and Taglab. In Nejran, north of Sana, and Yathrib there were also Christians. Arabian idolatry was very tolerant and afforded throughout the third and fourth centuries an equally safe asylum to the persecuted Zoroastrians, Jews and Christians who settled in various parts of the Peninsula. The kings of Himyar were themselves idolaters but allowed every other sect great freedom, including the Christians. But no sooner did the followers of Judaism gain power than persecution began. About the year 560, Dzu Nowass, ruler of Himyar, revolted against his lord the Abyssinian king, Elesbaan, and, instigated by the Jews, began to persecute the Christians. All who refused to renounce their faith were put to death without respect of age or sex, and the villages of Nejran were given over to plunder. Large pits were dug, filled with fuel, and many thousands of monks and virgins were committed to the flames.