Okay, Jesus has been exiled, Simon Peter goes back to his nets and dies of gangrene after getting his thumb amputated by a pike, and Saul of Tarses is walking down the Damascus road one day, staring into the sun, gets blinded, and walks off a cliff. A lot of people were seeing signs and omens in those days, and they probably would have just latched onto someone else. I believe that point has already been made. But what if they didn’t…?
Christianity didn’t really start to have an impact on history until there were enough of them to threaten the Empire’s dogma. 300 C.E., say, which I believe is the date that a previous poster gave as the approximate date of the wide acceptance of the Zoroastrian religion. Anyway, the Romans start losing ground in the East to the Parthians, and in these religion-starved lands, Zoroastrianism catches on. Piece by piece, the Parthians press their advantage, Egypt probably splits off and goes independent, a major economic blow. The fall of the West proceeds about as it does in this timeline, since the movement of the barbarin tribes has little to do with Christianity, at least at first. Constantine moves his capital to Byzantium, but he hasn’t embraced Zoroastrianism, since its influence has not been felt in Rome. Byzantium, on the other hand, is almost entirely converted. So probably what winds up happening is you have an Emperor who worships one set of gods, and a populace who worsips a god of a neighboring Empire. This, as you know, is not usually a good thing. The Parthians, taking advantage of this, conquer the Eastern Empire. They should have it all sown up by about the year 500.
Meanwhile, in the West, Rome has fallen, but nobody has converted to Christianity. The Germanic tribes who now rule Rome and its various provinces have their own set of gods, but it is one that can easily be reconciled with the Roman system. So they do essentially what the Romans did with the Greek system all those centuries ago: adapt it. Woden becomes identified with Jupiter, Thor with Vulcan, or maybe Mars, etc. After a while, they become assimilated, the Lombards in Italy, the Franks, Burgundians, and Alans in France, the Visigoths and Suevians in Spain, the Vandals in North Africa and Sicily, etc. A Germano-Roman renaissance of sorts begins, with thriving, cosmopolitan kingdoms. This probably brings them into conflict with the Parthians, and also the Egyptians, who are undergoing a renaissance of their own. It is right at this point that Mohammed shows up. What exactly he does, I will leave till next time, when I have figured it out.