It was located in the north of what would become Wales, adjacent to the island of Anglesey. With the withdrawal of Roman troops, and the fall of the local Romano-British administrators, Gaelic settlers from Ireland, who had already established a presence, intruded further into the area. In response, someone (sources differ on whether it was a quasi-Roman authority attempting to administer all of Britannia, or a local chieftain, either in Northern Wales or in the North-eastern quarter of Britain) invited or induced a Lothian clan-chief to migrate, with his family and war-band, to take up power in the area.
This was Cunedda, whose reported antecedents include a grand-father, Patern RedCloak, argued as a reference to the Roman practice of such cloaks for military officers, and a father called Eternus, a thoroughly Roman name, and un-Celtic. His migration is dated variously between 370 CE (when the Romans were still in Britain, and at a time when Magnus Maximus was trying to establish a regime separate from the main Roman one) and 440 CE (by which time the Romans were gone, and legend ascribes power to Vortigern), and he is given nine sons, one of whom did not migrate from Lothain, and several of the names of the others which have a curious resonance with Welsh locality names, and which may therefore be back-references to justify those names to later generations.
Cunedda's son, Einion is supposed to have expelled the Gaels from Angelsey, and his son, Cadwallon, is said the have flourished in the period after Mons Badonicus, when the Anglo-Saxon advance from the East is said to have been temporarily halted.
With Maelgwyn Hir (the Tall), son of Cadwallon, the story begins to edge toward history and although he was the last of Cadwallon's direct line to rule in Gwynedd, by his time it is arguable that a stable area had been consolidated under whatever rulers followed.
This amounted to the northern coast of Wales, from Chester west, to Angelsey, and then south, to the LLyn peninsula (possibly including the legendary and 'lost' Cantref Gwaelod), then east along the foot of the Snowdonian mountains, until reaching the shifting boundary with England proper.