Brycheiniog was an independent kingdom in South Wales in the Early Middle Ages. It often acted as a buffer state between England to the east and the south Welsh kingdom of Deheubarth to the west. It was conquered and pacified by the Normans between 1088 and 1095, though it remained Welsh in character. It was transformed into the Lordship of Brecknock and later formed the southern and larger part of the historic county of Brecknockshire. To its south was the Kingdom of Morgannwg.

The main legacy of the kingdom of Brycheiniog is etymological and geographical. It is used in Bannau Brycheiniog, the Welsh name for the Brecon Beacons range and, since 2023, in name used for the range's national park. Its name is also the origin to the anglicised names Brecknockshire (retained in Welsh as Sir Frycheiniog, 'the shire of Brycheiniog'), and Brecon (otherwise known as Aberhonddu in Welsh).

The kingdom of Brycheiniog was probably founded by Irish raiders in the late fifth century, very likely the Uí Liatháin, whose power had grown great in Wales until they were reduced by the sons of Cunedda (although this may just be propaganda for Gwynedd's power) as reported in the Historia Brittonum. Traditionally, it was founded by and named after a legendary Hiberno-Welsh prince named Brychan out of the old Welsh kingdom of Garth Madrun (believed to have been centered on Talgarth) in the mid-5th century, though this event is shrouded in legend. Brychan was a son of Anlach, an Irish settler who had peacefully taken control of the area by marrying Marchell, the heiress of Garth Madrun. Tradition says that Brychan fathered an extremely large number of children, many becoming saints in Wales and Cornwall. Brychan's eldest son (or grandson, depending on which manuscripts are reliable), Rhain Dremrudd (i.e. Rhain the red-faced), founded a dynasty which ruled the kingdom uninterrupted until the mid 7th century; manuscripts list his descendants (and successors) as:

During this era, the Irish raiders had begun to invade various western parts of Britain, with Triffyn Farfog (son of Aed Brosc [it], a Deisi magnate) already having taken over Dyfed from Edynfed's heirs. Traditional Welsh accounts claim that Triffyn had gained his power by peaceably marrying Edynfed's heiress (they do not indicate whether this was under duress). The power of Irish raiders, particularly the Uí Liatháin, grew increasingly strong, and was not weakened until it was reduced by the sons of Cunedda, as reported in the Historia Brittonum. However Irish presence remained in the south leaving many historians to theorise Cunedda faced strong resistance in the south.

Traditionally, Tewdrig carved out from his lands the region around Talgarth (Garth Madrun) as a dowry for his daughter, Marchell, when she married Brychan mac Anlach, the grandson of Triffyn's fraternal nephew, Cormac mac Urb, in the mid 5th century. The remainder of Tewdrig's lands — Gwent — was inherited by Tewdrig's son.

Historical sources of a much later date, such as the 12th century Book of Llandaff, name the next three generations of rulers of the eastern part — the descendants of Tudwal — as:

In the time of Idwallon, the aggressive Cynan Garwyn (king of Powys) invaded a number of lands, including Brycheiniog. Rhiwallon succeeded due to the subsequent collapse of Powysian power, under pressure from Dogfeiling, and the extreme youth of Cynan's later successor.

Rhiwallon is the last direct male descendant of Brychan reported by any historic manuscript. His daughter and heiress, Queen Ceindrych, married Cloten, the king of Dyfed. This 7th century marriage united the Kingdoms of Brycheiniog and Dyfed (which bordered each other at the time), a union which lasted for about a century (though parts of Brycheiniog may have been granted out, from time to time, as lordships for younger sons).