The first issue you should address in studying this is the distinction between faith in a modern sense, which has an element of fervent personal belief, and a more pragmatic ancient sense of "worship" as an outward conformity to the religion of a ruler. While Jews, Christians, and Muslims now have a sense of faith in which outward gestures of worship such as offering sacrifices (or even a pinch of incense) to a deity depended on some degree of deep conviction of the deity's existence and worthiness, in pagan societies, belief systems were much more fluid, admitting the existence of many different gods and taking a fairly pragmatic view of the value of worshiping (i.e. offering prayers and sacrifices) to any gods that might be useful. In the early stages of Islam, acceptance of the religion by pagans in conquered territory did not necessarily require any unique appeal of the belief system, but merely a pragmatic view that participating in the ceremonies of a religion mandated by local rulers was a sensible life choice. In general, conversion gradually followed conquest.
The spread of Islam was in part due to a power vacuum in the Arabian peninsula that resulted when the Persian and Byzantine empires focused on fighting one another. Abu Bakr, as the first Caliph, focused on subduing and uniting the Arabs under the banner of Islam. He succeeded in part due to two factors, wide support among the wealthy merchant classes, and a previous lack of unity among the tribes. Islam became a way for Arabs to unite and express cultural cohesion and identity. The philosophy of jihad also allowed this sense of unity and religious belief to express itself in the desire for conquest. Finally, Islam, with its clearly defined membership, gave fragmented societies a way to develop a sense of participation in a broader and more powerful community. Rather than nomads existing on the fringes of civilization (the great empires nearby), the Arabs, through conversion to Islam, gained a powerful identity of their own.