When the Roman garrison of Britain was withdrawn in 410, the various Brythonic states within Wales were left self-governing, as was the rest of Roman Britain. Evidence for a continuing Roman influence after the departure of the legions is provided by an inscribed stone from Gwynedd dated between the late 5th 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 colonization 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.
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 (which then became England). At the Battle of Chester in 613 or 616, the forces of Powys and other Brythonic 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 northern Brythonic kingdoms 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 Cornwall and Strathclyde.
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 and 7th centuries, 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 and control it for a period. Following Cadwallon's death in battle the following year, 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.