The Arab immigrants were not all merchants. Among them were those who moved in search of fertile pastures, water, and fodder, and for the propagation of Islam. From here, they found the vast expanses of Sudan to spread their message, as they found ample space within its territories. Moreover, the nature of Sudan resembled the nature of their homelands in every way. The Red Sea is merely a geological fold in one land, splitting it into two parts: Sudan and the Arabian lands. Therefore, they resembled each other in plains and valleys.

It is known that groups of Sabaeans, since the fifth century BC, had migrated from southern Arabia to the western coasts of the Red Sea and initially settled on the islands of this sea, such as Socotra and others, and then spread widely along the eastern shores of the African continent. From here, they established routes for caravans to facilitate the movement of camels to the interior regions. Their objective at that time may have been twofold: to expand the scope of their commercial activities and to attempt to escape the harsh coastal climate. To this day, the names of some places located near Massawa and Assab bear witness to the Sabaean advance into these interior African regions.

In addition to this, it is said that Arab tribes from Bali had migrated to the land of Beja long before the advent and appearance of Islam. Furthermore, the sixth century AD witnessed a large Arab migration to the land of Beja, undertaken by some Hadramis who settled in the land of Beja. These Hadramis mingled and intermarried with those from the tribes of Bali who would later move to those regions.

These Hadramis and the Bali were among the Beja who embraced Islam quickly, unlike the rest of the Beja. To this day, the Beja still refer to the Arabic language by saying "Balawit," meaning that the Arabic language is the Balawi language, named after the tribe of Bali who brought Arabic to them.