The history of their migration to Sudan is shrouded in much mystery, like the history of most Arab tribes that migrated to Sudan. However, the migration of the Rashayda was the most recent Arab migration to Sudan, as they arrived from the Arabian Peninsula to the western coast of the Mediterranean Sea in the late nineteenth century AD.

This migrating tribe was known by two names in Sudan. The first name, which is the most common and prevalent, is Al-Rashayda. As for the second name, it is Al-Zubaida. Some elders of this tribe, who are over seventy years old, explain that the secret to this dual name (Al-Rashayda and Al-Zubaida) is that they are descendants of the Abbasid Caliph Harun al-Rashid and his wife Zubaida, the owner of Zubaida's well in 'Arafah. From Al-Rashid they derived their first name, and from Zubaida they derived their second name. They are divided into three main branches: Al-Barasi'a in the east, Al-Baratiikh, and Al-Zuniyat. There are seventeen generations between them and the great-grandfather who came to Sudan, reaching the name Harun al-Rashid.

Those who visited the Arabian Peninsula in the nineteenth century consider them among the authentic Arab tribes. In the Arabian Peninsula, they have main branches: Al-Shurafat, Aqabiisi, and Banu Rashid. The ancestor of Al-'Utaym, who live in the central region of the Arabian Peninsula, is Al-Rashid. There might be a connection between the Rashayda and the Al-Rashid family, who contested the rule and influence of King Abdulaziz bin Abdul Rahman Al Saud in Riyadh. Among them are Al-Haytham, who live on the Red Sea coast near the port of Al-Wajh (Al-Wushn). They claim kinship with Quraibees, and these might be the ones from whom a portion migrated to Sudan. Some of Al-Haytham live in Tihamah, north of Mecca Al-Mukarramah. What strengthens the argument for a connection between the Rashayda and Al-Haytham is that Al-'Awazim or Al-'Awazimah, who migrated to Sudan with the Rashayda and came under the command of Al-Zuniyat, are originally part of Al-Haytham. 251