The Northern Uí Néill's over-kingdom in its earliest days was known as In Fochla and In Tuaiscert, both meaning "the North", and was initially ruled by the Cenél Conaill. After the Cenél nEógain's rise to dominance, it became known as Ailech.
It is claimed in medieval Irish texts that around 425, three sons of Niall Noígiallach—Eoghan, Conal Gulban, and Enda—along with Erc, a son of Colla Uais, and his grandchildren, invaded north-western Ulster. The result was the vast reduction in the territory of the Ulaid, with the portion of land taken by the three sons of Niall becoming the kingdom of Ailech. This land was divided between the three brothers as such: Conal Gulban took the western portion and named it Tír Chonaill; Eoghan took possession of the main peninsula and named it Inis Eoghain; Enda took nominal possession of land lying south of Ailech, which became known as Magh Enda.
The lack of contemporary evidence has cast doubt on the validity of traditional accounts, with questions raised whether such an invasion actually took place, as well as whether the invaders even belonged to the Uí Néill at all.
From the 8th century onwards, likely sponsored by Áed Allán, a Cenél nEógain king of Tara, and Congus, the bishop of Armagh, early Irish historians carefully constructed propaganda to shore up and cement Uí Néill political supremacy along with the ecclesiastical supremacy of Armagh. This involved the ruthless re-writing and doctoring of genealogies, lists of kings, history, and early annals, tracing the current situation as having primacy all the way back into the undocumented 5th century. In tandem, about a dozen peoples became designated within what was called Uí Néill in Tuaiscirt, of which the Cenél Conaill and Cenél nEógain were the most dominant.