Early medieval Ireland was layered into a shifting hierarchy of political entities the content and boundaries of which remain largely unknown. The earliest divisions of which we are aware are the cóiceda ('fifths'). That Ireland was anciently a pentarchy is indicated by the use throughout the historic period of the term cóiceda to describe the provinces even though they numbered other than five. From an examination of tribal and dynastic origin-legends embedded in the early narrative literature the five prehistoric cóiceda would seem to have been Ulaid ('Ulster'), Mumu ('Munster'), Laigin ('Leinster'), Connachta ('Connacht') and Mide ('Middle'). These prehistoric cóiceda may be broadly equated to the four modern provinces of Ulster, Munster, Leinster and Connacht saving territory for a fifth province now vanished of unknown extent lying at their intersection. This scheme may be restored to create the territorial position prior to an event that can then be presumed as the earliest knowable event in Irish history, the breaking of this ancient scheme by sons of Niall Noígiallach upon their conquest of a large part of western Ulster in the fifth century. Shown in the seventh century regnal list Baile Chuinn Chétchathaig ('Ecstatic Vision of Conn of the Hundred Battles') as having held the nationally important sacral kingship of Tara around the middle of the fifth century, Niall's own origins will forever remain obscure for want of historical records but to the faint reverberation of ancient battles men who by their patronymics are clearly his sons and grandsons emerge from prehistory into the earliest stratum of the Annals of Ulster as the Uí Néill ('Descendants of Niall'), a young dynasty already in possession of the kingship of Tara and an arc of cross-provincial territory extending from Tara in northern Leinster through northern Connacht to Inishowen in western Ulster.
By the eleventh century the dominant political entity in the north of Ireland was Tír nEoghain ('Land of Eoghan') which was the territory directly ruled by the leader of the Cenél nEoghain. An unravelling of references to this territory and its rulers in the annals, saints' lives and genealogies indicates an origin in a petty kingdom on the Inishowen peninsula ruled by Eoghan son of Niall who died in 465 . Lying to the east was an area occupied by a people known as Airgialla ('Hostage-givers') who seem to have been a loose grouping of tribes once tributary to Ulaid that buffered the eastern remnants of Ulaid from the encroaching Uí Néill. At a very early date the petty kingdom appears to have expanded its territory eastward across the river Foyle into the Airgialla territories delimited by the Sperrin mountains so that by the time of the battle of Móin Daire Lothair in 563 it was in a position to expand further eastwards across the Sperrin mountains into the Ulaid territories of Lee and Ard Eolairg delimited by the rivers Moyola and Bann . This expanded area formed the basis of the territory later described as Tír nEoghain north of the mountain but the process of further expansion south of the mountain Slieve Gallion to form the territory described as Tír nEoghain south of the mountain is less clear. While it is thought that all of Airgialla came under the influence of a firm Cenél nEoghain overlordship after the battle of Leth Cam in 827  it is known that by the ninth century the territory of Tír nEoghain had expanded south of the Sperrin mountains to include the former Airgialla territories around Bodoney on the Glenelly river  and by 1012 had expanded south of Slieve Gallion to include the former Airgialla territories around Tullaghoge on the western shores of Lough Neagh . The remnant of Ulaid lying east of the river Bann then came under the influence of an intermittent Cenél nEoghain overlordship until the twelfth century when it was divided into separate lordships made immediately subject to the MacLochlainn rulers of Tír nEoghain .
The growth of territory and influence in the east led to an increase in Cenél nEoghain influence to the west in Tír Conaill ('Land of Conall') which was the territory of the Cenél Conaill ('People of Conall'). An unravelling of references relating to this territory and its rulers indicates an origin in a petty kingdom ruled by Conall son of Niall Noígiallach on the peninsulas and hinterlands lying west of Inishowen though his existence is unattested until 586 . By the seventh century this petty kingdom had expanded south to include the territory of Magh Iotha delimited to the north by the estuary of the river Swilly and elsewhere by the western basin of the river Foyle . By the ninth century it extended to Assaroe in the south but by that time opportunities for further territorial growth had been limited by the expansion of Tír nEoghain southward into Magh Iotha . Prior to the seventh century Magh Iotha would seem to have been the territory of the elusive Cenél nÉndae ('People of Énna') whose slender genealogical remains ascend to an otherwise unattested Énna son of Niall Noígiallach whose petty kingdom this may once have been. It was to remain highly contested between the Cenél Conaill and Cenél nEoghain and one is left with the strong impression that the border here changed frequently, one such border being preserved in the boundary between the dioceses of Raphoe and Derry that has bisected the area since the twelfth or thirteenth century. From sometime before 563 the Cenél nEoghain had joined with the Cenél Conaill (and presumably the Cenél nÉndae) in a northern Uí Néill overkingdom of In Tuaisceart ('The North')  which was in turn joined with the southern Uí Néill under the kingship of Tara. A cross-referencing of annals and genealogies shows that the overkingship of The North was held between the Cenél nEoghain and the Cenél Conaill but by the ninth century the increased resources that became available to the Cenél nEoghain shifted the balance of power to such an extent that the Cenél Conaill were excluded from the overkingship thereafter . From the ninth century the overkingdom is increasingly referred to as Aileach, from the tenth and eleventh centuries a new segmental nomenclature Tír nEoghain/Tír Conaill is applied to the territories lying within and in the twelfth century Tír Conaill is made immediately subject to the MacLochlainn rulers of Tír nEoghain .