So one of the more interesting points in Yemeni history is the Jewish Himyar kingdom - which converted under Abu-Kariba. However, with Jews being persecuted in Aksum, Himyar persecuted Christians in Himyar.
What if instead of dying before his sons were fully grown, he lived long enough to secure a smooth succession, and ruled for tolerance - the basis being that at Yathrib, the Jews fought alongside Pagans. So Christian, Pagan, and Jew can all fight as men of Himyar - even if Jews get preferential treatment.
Could it butterfly an invasion from Aksum? Lead to a strong Jewish Arabia?