When Muhammad died, there were immediate problems among the Muslim Arabs. He did not name a successor, but he had been the definitive leader of the Islamic community during his life; it seemed clear that the community was meant to have a leader. The Muslim elders appointed Muhammad's father in-law, Abu Bakr (r. 632 – 634), as the new leader after a period of deliberation. He became the first Caliph, meaning "successor": the head of the Ummah, the man who represented both spiritual and political authority to Muslims.
Under Abu Bakr and his successors, Umar (another of Muhammad’s fathers in-law; r. 634 - 644), and Uthman (r. 644 – 655), Muslim armies expanded rapidly. This began as a means to ensure the loyalty of the fractious Arab tribes as much as to expand the faith; both Abu Bakur and Umar were forced to suppress revolts of Arab tribes, and Umar hit upon the idea of raiding Persia and Byzantium to keep the tribes loyal. For the first time in history, the Arabs embarked on a sustained campaign of conquest rather than serving others as mercenaries.
Riding their swift horses and camels and devoted to their cause, the Arab armies conquered huge amounts of territory extremely rapidly. It was the Arab army that finally conquered Persia in 637 (although it took until 650 for all Persian resistance to be vanquished), that hitherto-unconquered adversary of Rome. The Arabs conquered Syria and seized Byzantine territory in Anatolia equally quickly: Egypt was conquered by 642, with an attempted Byzantine counter-attack fought off in 645. Within twenty years of the death of Muhammad, the heartland of the Middle East was firmly in Arab Muslim hands.
Part of the success of the first decades of the Arab conquests was because of the vulnerability of Byzantium and Persia at the time, and another part was the tactical skill of Arab soldiers. The Arabs conquered Persia not just because it was weakened by its wars with Byzantium (most importantly its defeat by Heraclius in 627), but because many Arab clans had fought as mercenaries for both sides in the conflict; great wealth had been flowing into Arabia for decades, and the Arabs were already veteran soldiers. They had learned both Roman and Persian tactics and strategy and they were skilled at siegecraft, intelligence-gathering, and open battle alike.
The Arab armies were easily the match of the Byzantine and Persian forces. The Arabs were able to field armies of about 20,000 – 30,000 men, with a total force of closer to 200,000 by about 700 CE. Most were Arabs from Arabia itself, along with Arabs who had settled in Syria and Palestine and were then recruited. A smaller percentage were non-Arabs who converted and joined the armies. Tactically, the majority were infantry who fought with spears and swords and were lightly-armored.
The major tactical advantage of the Arab armies was their speed: horses and camels were important less as animals to fight from than as means of transportation for the lightly-armored and equipped armies. Soldiers were paid in coins captured as booty and whole armies were expected to buy their supplies as they marched rather than relying on heavy baggage trains. Their conquests were a kind of sustained sprint as a result. Likewise, one specific military "technology" that the Arabs used to great effect was camels, since no other culture was as adept at training and using camels as were the Arabs. Camels allowed the Arab armies to cross deserts and launch sudden attacks on their enemies, often catching them by surprise.
Finally, especially in Byzantine territories, high taxes and ongoing struggles between the official Orthodox form of Christianity and various other Christian sects led many Byzantine citizens to welcome their new Arab rulers; taxes often went down, and the Arabs were indifferent to which variety of Christian their new subjects happened to be. In addition, the Arabs made little effort to convert non-Arabs to Islam for several generations after the initial conquests. To be clear, there was plenty of bloodshed during the Arab conquests, including the deaths of many civilians, but the long-term experience of Arab rule in former Byzantine territories was no more, and probably less, oppressive than it had been under Byzantium.