Even before Islam, the Pre-Islamic Arabian Pantheon was being condensed into a Tritheistic form, with worship largely becoming centered around Allah (the Arabic Pagan Creator God, not Islamic Allah), Manat (the Goddess of fate, fortune, time, death, and destiny and one of the few Arabic Gods that Muhammad thought existed as a powerful entity, but not as a real g God according to some sources) and Al-Uzza (Goddess of Might and Protection, and like her sister, Manat, was considered a real entity by Muhammad and Khalid as well via some sources). Other gods like Al-Lat, Hubal, Haukim, and Bes were starting to take on a more Angel like role in Arabic Paganism organically according to the inscriptions at Abd Shams, rather than being actual Gods themselves, though with Al-Lat it was more foggy because her sisters Al-Uzza and Manat were revered above even Allah many times, especially Manat. Muhammad, reportedly, said that Manat was the strongest pre-Islamic God of the Arabs, according to the writings of Ibn al-Kalbi
So a united Tritheistic Belief rising out of Arabia, matching the time period of the Roman-Persian War at the Arabic Demographic Boom at the same time or nearly the same time and taking advantage of the weakened Romans and Persians to expand isn't out of the question. If they can expand into the horn of Africa as well - there is some evidence of Pagan Arabic influence on ancient Eritrea, Djibouti and Somaliland - then they could become a strong contender for a nearby strong religious rival.