Oral traditions assert its establishment to refugees from the Nubian Kingdom of Alodia, after its capital Soba had fallen to Arabs or the Funj in c. 1500.

In the Middle Ages, large parts of central and southern Sudan, including the region of Fazughli on the border with Ethiopia, were controlled by the Christian Nubian Kingdom of Alodia.

[13] Using oral traditions, Spaulding continues to argue that the Alodians eventually abandoned the territory they still held in the lower Blue Nile valley and retreated to the mountainous region of Fazughli in the south, where they reestablished their kingdom.

[12] One tradition collected in the 19th century, for example, recalls that: the kings of Fazughli, whose dominion extended over a large part of the peninsula of Sennar (the Gezira), and one of whose capitals had been the ancient Soba, had been forced to give way before the new arrivals... the Funj ... and to retire to their mountains...

[20] It has been warned that the traditions linking Fazughli to Alodia may not necessarily be factual, but were rather supposed to legitimize the rule of the Fazughlian king.

[23] A Portuguese source from 1607 states that it had "much fine gold and good horses exchanging trade with the (Ethiopian) empire.

"[27] Another one published in 1622 records that "(...) it is certain fact, as everyone says and Emperor Seltan Cagued (Susenyos) has told me, that the finest gold in all his lands is from the kingdom of Fazcolo".

[29] Nevertheless, the period from the late 15th to early 17th century would have been a troubled one for the Ethiopian-Sudanse borderlands, as is reflected by the "Jebel Mahadid tradition" settlements, which were not only located on naturally defended positions, but were also protected by additional defensive systems.

[30] Dakin was defeated and when he returned to Sennar he was confronted with Ajib, an ambitious minor prince of northern Nubia.

[42] In 1761–1762[43] Muhammad Abu Likayik, a military commander originating from Fazughli, assembled a "heterogenous collection of neo-Alodian noblemen, warlords, slave soldiers, merchants, and fuqara (religious teachers)"[44] and seized control of the sultanate, initiating the Hamaj Regency, which lasted until the Turko-Egyptian invasion of 1821.