Feast of Saint Harit (Arethas) and His Companions

In the Maronite Calendar of Saints, today is the feast of St. Harit (Arethas to the Greeks). St. Harit was born, according to tradition, in 427. He was a starets (elder) and held the post of Governor of Nadjran. He was martyred at the age of 95, in the year 523.

(From Catholics Online)
In the sixth century, the king of Yemen, Dzu Nowass, a convert to Judaism, undertook a violent persecution against the Arab Christians under his rule, demanding that they convert to Judaism. To the largely Christian city of Nadjran the king sent a messenger bearing a pole-mounted cross and conveying this ultimatum: “Whosoever will not show insult to this sign shall be destroyed by fire and sword. Whosoever remains Christian…shall perish by fire and sword…Therefore, citizens of Nadjran, choose my favor, or your religion of the Crucified.” Following the people’s refusal to deny their faith, the king ordered a series of massacres. 427 priests, deacons, monks, consecrated virgins, and lay Catholics were thrown in pits and burned to death. The city’s governor, Prince Arethas, known to Arab historians as Abdallah Ibn Althamir (Harit to the Maronites), was beheaded. A far larger massacre followed, in which over four thousand of the faithful were slain in various ways. As the head veils were stripped from a Christian noblewoman and her two daughters in preparation for their beheading, the Jewish women among the spectators wept in sympathy for the martyrs.

So in 523, large parts of the Arabian Peninsula were Christian and / or Jewish. Gee, I wonder how they became Islamic only a century or so later? Did they have an election?