Deheubarth was united around 920 by Hywel Dda out of the territories of Seisyllwg and Dyfed, which had come into his possession. Later on, the Kingdom of Brycheiniog was also added. Caerleon was previously the principal court of the area, but Hywel's dynasty fortified and built up a new base at Dinefwr, near Llandeilo, giving them their name.
After the high-water mark set by Hywel, Dinefwr was repeatedly overrun. First, by the Welsh of the north and east: by Llywelyn ap Seisyll of Gwynedd in 1018; by Rhydderch ab Iestyn of Morgannwg in 1023; by Gruffydd ap Llywelyn of Gwynedd in 1041 and 1043. In 1075, Rhys ab Owain and the noblemen of Ystrad Tywi succeeded in treacherously killing their English-backed overlord Bleddyn ap Cynfyn. Although Rhys was quickly overrun by Gwynedd and Gwent, his cousin Rhys ap Tewdwr – through his marriage into Bleddyn's family and through battle – reëstablished his dynasty's hegemony over south Wales just in time for the second wave of conquest: a prolonged Norman invasion under the Marcher Lords. In 1093, Rhys was killed in unknown circumstances while resisting their expansion into Brycheiniog and his son Gruffydd was briefly thrown into exile.
Following the death of Henry I in 1136, Gruffydd formed an alliance with Gwynedd for the purpose of a revolt against Norman incursions. He took part in Owain Gwynedd and Cadwaladr ap Gruffydd's victory over the English at Crug Mawr. The newly liberated region of Ceredigion, though, was not returned to his family but annexed by Owain.
The long and capable rule of Gruffydd's son the Lord Rhys – and the civil wars that followed Owain's death in Gwynedd – briefly permitted the South to reassert the hegemony Hywel Dda had enjoyed two centuries before. On his death in 1197, though, Rhys redivided his kingdom among his several sons and none of them ever again rivalled his power. By the time Llywelyn the Great won the wars in Gwynedd, in the late 12th century, lords in Deheubarth merely appear among his clients.
Following the conquest of Wales by Edward I, the South was divided into the historic counties of Cardiganshire, Carmarthenshire and Pembrokeshire by the Statute of Rhuddlan.