When the Roman garrison of Britain was withdrawn in 410, the various British states were left self-governing. Evidence for a continuing Roman influence after the departure of the Roman legions is provided by an inscribed stone from Gwynedd dated between the late 5th century and mid 6th century commemorating a certain Cantiorix who was described as a citizen (cives) of Gwynedd and a cousin of Maglos the magistrate (magistratus). There was considerable Irish colonisation in Dyfed in south-west Wales, where there are many stones with Ogham inscriptions. Wales had become Christian, and the "age of the saints" (approximately 500–700) was marked by the establishment of monastic settlements throughout the country, by religious leaders such as Saint David, Illtud and Teilo.
Gravestone of King Cadfan ap Iago of Gwynedd (died c. 625)
One of the reasons for the Roman withdrawal was the pressure put upon the empire's military resources by the incursion of barbarian tribes from the east. These tribes, including the Angles and Saxons, who later became the English, were unable to make inroads into Wales except possibly along the Severn Valley as far as Llanidloes. However, they gradually conquered eastern and southern Britain. At the Battle of Chester in 616, the forces of Powys and other British kingdoms were defeated by the Northumbrians under Æthelfrith, with king Selyf ap Cynan among the dead. It has been suggested that this battle finally severed the land connection between Wales and the kingdoms of the Hen Ogledd ("Old North"), the Brythonic-speaking regions of what is now southern Scotland and northern England, including Rheged, Strathclyde, Elmet and Gododdin, where Old Welsh was also spoken. From the 8th century on, Wales was by far the largest of the three remnant Brythonic areas in Britain, the other two being the Hen Ogledd and Cornwall.
Wales was divided into a number of separate kingdoms, the largest of these being Gwynedd in northwest Wales and Powys in east Wales. Gwynedd was the most powerful of these kingdoms in the 6th century and 7th century, under rulers such as Maelgwn Gwynedd (died 547) and Cadwallon ap Cadfan (died 634/5), who in alliance with Penda of Mercia was able to lead his armies as far as Northumbria in 633, defeat the local ruler Edwin and control it for approximately one year. When Cadwallon was killed in battle by Oswald of Northumbria, his successor Cadafael ap Cynfeddw also allied himself with Penda against Northumbria, but thereafter Gwynedd, like the other Welsh kingdoms, was mainly engaged in defensive warfare against the growing power of Mercia.