In the 6th century, the people who now form the Jebeleya tribe, were sent as soldiers and servants from Wallachia and Alexandria to the Sinai high mountains by the emperor of the Roman-Byzantine empire, Justinian (527-565), to protect and serve the Sinai Monastery.
The Jebeleya tribe is now recognized as Bedouin but their origin is not from Arabia like all other Sinai Bedouin tribes.
According to geographical writings from the 10th century, the Beyyedhiyin and Bili, along the Mediterranean Sea in the North Sinai, are the oldest tribes.
From 14th century writings it's clear that different strains are now assimilated into larger contexts and some of these are the Amarin, Habaniyin and Ghuyuth (now part of the Suwarkah in the northeast), the Jubarat (now in Gaza), the Beni Wasil (in the south) and the Badarah (in the middle of Sinai).
From scriptures we learn that the Beni Wasil is the oldest tribe of Arab origin of South Sinai, followed by the Sawalhah and Hamayda. Later (from 1400) the Aleygat and many years after the 'Muzaynah' (late 15th century). In the 18th century the 'Tarabin', who conquered much land from other tribes in the north, west, east and south of the Sinai, were known.
Sources: Survey of C. Bailey, R. Pococke, The administration Monastery St.Katherine and research of L. Winter Roeder Jr.
For many years there were revenge and blood feuds. These conflicts ended in sword fights and were handled under El Orf, the Bedouin legal system.
Internal conflicts over land were and are solved with the help of the Monastery of St. Katherine, where records are kept by the monks for the Bedouin.
Alliances between tribes are formed for great(er) interests. For example, the Hamayda is related to the Aleygat, which in their turn again allied with the Muzaynah and there is an alliance of the Sawalhah, Gararsha, Jebeleya, Huwaytat, Beni Wasil and Owled Said.
The members of the various Bedouin tribes now live together in different areas in the Sinai, which is a vast area and where everyone was always free to settle.
There were never any special areas owned by someone other than the fertile wadis that were considered to be the territory of a particular tribe.
Because most lived a nomadic or semi-nomadic life, they lived where water could be found. This is different nowadays, as certain tribes now make claims to certain tourist attractions (income) which is cause for friction.
Source: BEDAWI - M.I.M. Sabbah & R. W. de Jong