One factor was clearly the demise of the Roman empire, creating a political vacuum among formerly united peoples. Another was the elimination of deep rooted pagan religious ties in that area in favor of another Abrahamic religion with its roots in Semitic peoples: Christianity, which is itself an sect of Judaism historically.
The Plague of Justinian
Another lesser known circumstance that made the areas it conquered ripe for conquest was the Plague of Justinian, caused by the same pathogen as the Black Death that afflicted Europe in the Middle Ages, brought to Europe and the Near East via invaders from Central Asia (perhaps the Turkic Huns who have origins in Northeast Asia) or Silk Road traders, and ultimately from China. New genetic evidence from ancient DNA published in Nature Genetics shows that the "first outbreak of plague occurred in China more than 2,600 years ago before reaching Europe via Central Asia's "Silk Road" trade route." The date would coincide with the Spring and Autumn period of the Eastern Zhou Dynasty in China although I can't find any reference to an outbreak (other than a locust plague) in this well documented historical time and place.
The Plague of Justinian was a pandemic that afflicted the Eastern Roman Empire (Byzantine Empire), including its capital Constantinople, in the years 541–542. . . Modern scholars believe that the plague killed up to 5,000 people per day in Constantinople at the peak of the pandemic. It ultimately killed perhaps 40% of the city's inhabitants. The initial plague went on to destroy up to a quarter of the human population of the eastern Mediterranean. New, frequent waves of the plague continued to strike throughout the 6th, 7th and 8th centuries CE, often more localized and less virulent. It is estimated that the Plague of Justinian killed as many as 100 million people across the world. Some historians such as Josiah C. Russell (1958) have suggested a total European population loss of 50% to 60% between 541 and 700.
After 750, major epidemic diseases would not appear again in Europe until the Black Death of the 14th century.
This had a powerful effect on the fate of the Byzantine Empire:
Byzantine Emperor Justinian I had expended huge amounts of money for wars against the Vandals in the Carthage region and the Ostrogoth kingdom of Italy. . . .As the disease spread to port cities around the Mediterranean, it gave the struggling Goths new opportunities in their conflict with Constantinople. The plague weakened the Byzantine Empire at a critical point, when Justinian's armies had nearly wholly retaken Italy and the western Mediterranean coast; this evolving conquest could have credibly reformed the Western Roman Empire and united it with the Eastern under a single emperor for the first time since the year 395. The plague may also have contributed to the success of the Arabs a few generations later in the Byzantine-Arab Wars. . . . When the plague subsided, [Justinian] retook Italy, but could not move further north. The eastern empire held Italy for the remainder of Justinian's life, but the empire quickly lost all territory except the southern part after he died. Italy was ravaged by war and fragmented for centuries as the Lombard tribes invaded the north.
The forcible end of pagan religious practice and unorthodox Christian practice, also left communities with thin traditional ties to their current religion (Christianity), leaving more room for mass conversion to a new faith. Christianity was officially tolerated in the Roman empire during the reign of Emperor Constantine 306-337 AD, who convened the Council of Nicaea in 325 to establish what was orthodox Christian doctrine. All dissenting Christian views were banned and forcibly rooted out in the reign of Emperor Theodosius I (378-395) and it is largely to him that we owe the destruction of most Gnostic and pagan texts and religious relics and temples (including those not destroyed in the first sack of the library of Alexandria by Julius Caesar in 47 BC), and the decline of those faiths within the Roman Empire.
In the Byzantine Empire, a new schism between orthodox Christianity and Monophysitism (which was labeled a heresy and drifted in the direction of gnosticism). Monophysitism was strongest in Syria and Egypt, and disappeared when these areas came under Islamic control in the mid-600s CE. Thus, the hold of the Orthodox Church on the areas that were invaded by Islam was already weakened and the subject of political tensions.
The Timing Is Right
How does this coincide with the rise of the Islamic empire?
In 597, Muhammed was an unknown man in his 20s. Around 622, when he left Mecca, his movement was starting to gather steam. By 632, at his death, Islam was a force to be reckoned with.
Caliph Omar had conquered Alexandria in 640 AD but the library was nothing but an ancient ruin, although Islamic rule further suppressed pagan practice that has survived persecution by Roman Christians. Syria and Egypt had both fallen to Islam by 655, followed by the Shiite and Sunni split in the form of a civil war from 655-661. All of North Africa had been conquered by the 690s.
The same era of Chinese history that first encountered the plague also gave rise to the crying wolf tale of China from the 700s BCE:
The case of King Youwang 周幽王 gives nourishment to the Confucian writers who blame him to have followed the words of his consort Baosi, thus making him equal to King Zhou (Zhow) 商王紂 of the Shang Dynasty and tyrant Jie 夏王桀 of the mythical Xia Dynasty. King You had established a warning system of towers that had to light a fire when the barbarians would attack. Baosi abused this system just for fun. When the Quanrong nomads 犬戎 (i.e. Xuanyuan) really attacked, nobody hurried to the weapons.