The early Caliphs were not as interested in governance as in expansion. They wanted tribute; they were content to use force to exact it and then move on. Local rulers were mostly left in place, with local customs. However, as they found by the 3rd Caliph’s reign, it was necessary to have more people on the ground in local government in order to keep down rebellions.
The early Caliphs were also very interested in conversions. Islam already had a short history of co-existence with Jews and Christians. Their ire was reserved for idolaters, for people whose lives were not guided by Abrahamic scriptures. Persian Zoroastrians were a gray area: were they worshipers of fire, or were they philosophical people of a Book? Their treatment shifted, but their eradication by one means or another went much faster than that of Jews and Christians. Sometimes they were taxed, sometimes they were forced.
In their early conquests, the Armies of God went into the mostly Christian lands of Syria and Egypt, and then into Persia and the outskirts of India. By 664, an advance army headed farther east into Sindh, an area of India, and into what’s now Afghanistan. There, local religions were considered idolatry. By 712, all of what’s now Pakistan was Muslim, and some of northern India.
The original tax formula was set up to use conquered people to support the Companions of Mohammed back in Arabia. Everyone paid taxes, but the tax rate was discriminatory against non-Muslims, since they were conquered people paying tribute. Of course, pagans were converted or dead, so non-Muslims were only Jews and Christians. The tribute burden fell on them.
Over time, nominal and opportunistic Jews and Christians became Muslims to get the tax break. After an area had been in the Caliphate for a generation, it was mostly Muslim and the tax revenue headed to Damascus and Mecca dropped. This created a fiscal problem.
There were two other key discriminatory provisions. Since the foundation for truth was that Mohammed was the Prophet, anyone who did not make that confession was already a liar. Non-Muslims were not permitted to testify against Muslims in the city courts. It’s not hard to imagine the commercial discrimination that resulted. The other discrimination was about houses of worship. When churches were not wanted as mosques, synagogues and churches could stand. But they could not be built or rebuilt. Slowly, houses of worship fell into disrepair, making local Jews and Christians ashamed of their religion compared to the mosque-going neighbors.
Discrimination drove military expansion. The tax base had to be expanded in every generation. Local Arab generals in Egypt, Syria and Persia had incentives to push their borders outward. From Egypt, they expanded into Nubia. Military expeditions failed, by and large, in this area (now Sudan). But they concluded a peace treaty and established trade relations; Sudan gradually adopted Islam voluntarily.
Egypt-based armies expanded widely across North Africa, quickly conquering its hinterlands and coastal cities. Using Tunis and Tripoli as naval bases, they conquered the major islands of the Mediterranean: Crete, Cyprus and Sicily, as well as many smaller islands.
Caliph Muawiya (the antagonist of Ali’s family) laid siege to Constantinople, first by taking smaller islands and ports, building up naval power. But Constantinople was able to drive off the attackers by using Greek fire for the first time. Greek fire is the first known chemical weapon. It burst into flame on contact, and water did not quench it. Lobbing Greek fire at the Arab ships, the Byzantines destroyed their navy. A second, more careful, siege in 718 was also defeated. Constantinople prevented the Arabs from entering southern Europe by land. (At this time, modern Turkey was not yet conquered either.)
One hundred years after Mohammed first began to see visions, Arab armies in North Africa were poised to use Morocco as a launching point to begin conquest of Europe. Between 711 and 718, most of Visigothic Spain fell to the invaders.
Meanwhile, Cairo became the chief Muslim city of Egypt, and the Umayyad Caliphs ruled from Damascus.