The history of Wales in the wake of the Romans is beset by a monumental lack of plausible written documentation. In other words, it's awfully hard to say for certain what happened. With that disclaimer established, let's take a look at what we think we know about a period that was to a large degree essential to the establishment of Welsh culture.
It seems likely that Wales initially was divided into numerous small kingdoms under the control of the leading families of the former Romano-British aristocracy. Several traditions state that new Welsh leaders came from among the "Men of the North" (i.e. Scotland). Certainly, there were ties of culture between the British of the north and in Wales.
The most powerful of the early Welsh kings in the north was Maelgwn Gwynedd, possibly a descendant of Scottish settlers.
If the early kingdoms of northern Wales owe a debt to the Scots, those of the south owe a similar debt to the Irish. The area of Dyfed was heavily colonised by Irish settlers in the last years of the Empire and the decades which followed.
The kingdom of Powys incorporated the lands of the Cornovii tribe and those of the royal family of Gwryheyrnion, while the former lands of the Silures became the foundation for the kingdom of Gwent. To the north lay Erdig, and to the west Glwywysing. Eventually, Glwywysing, under the king Meurig and his descendants, extended control over Gwent and Erdig to form the new kingdom of Morgannwg (Glamorgan).
A shadowy figure in the early legends of the Welsh kingdoms is Magnus Maximus (Macsen Wledig of the Mabinogion), who appears in the genealogies of several kingdoms. Magnus Maximus was a Roman official who may have been responsible for the final withdrawal of Roman troops from Wales, possibly in 383AD, as part of his attempt to seize control of the Empire. He was briefly successful in his bid, and he ruled in the West for several years before he, in turn, was cast down.
From these moderately factual beginnings, the legend of Macsen Wledig grew until later scholars credited him with being the founding father of the Welsh nation, which is stretching the facts a bit TOO thin.
One of the British leaders after the departure of the Romans was Vortigern (Gwyrtheryn of Welsh legend), who may have been a native of the Welsh borders. Certainly, the kings of Powys claimed him as an ancestor. It was Vortigern who is blamed for inviting Saxon mercenaries into Britain to help maintain order in the period following the departure of Roman troops. When the money ran out to pay the mercenaries, they rebelled and over the course of several centuries, took over control of large sections of Britain from the Romano-British.
One of the leaders of the British resistance to the Germanic tribes we now call English was Ambrosius (Emrys Wledig in Welsh legend). Ambrosius is likely to have come from the Romano-British aristocracy, and there is some suggestion that he was a rival of Vortigern.
Ambrosius is closely associated with the legends of King Arthur. Some scholars have argued that he IS Arthur, others that Arthur was a war leader for Ambrosius. Ambrosius/Arthur or a similar Romano-British leader marshalled the British forces against the Saxons.
Sometime around 496 AD, the advance of the Saxons was halted, perhaps at a battle called Mons Badonicus. Although the specifics of the battle are not known, and even its reality is questionable, archaeological excavations have shown that the Saxons were pushed back for a short time, and some left Britain to settle on the continent again.
But the check to their advance was only temporary. By 550 several areas of Saxon dominance had been established; notably in the southeast of England, and in Northumbria. Sometime around 550 the kings of Saxon Wessex began a series of campaigns which steadily pushed back the British.