The Venedotian Code of the Welsh laws compiled by Iorwerth ap Madog in the early 13th century^[6] contains a list of the privileges of the men of Arfon. Among the privileges is the right to march in the van of Gwynedd's army, and this is stated to originate from their spirited actions in a war between Rhun of Gwynedd and the Cymric Men of the North (Welsh: Gwŷr y Gogledd) from the kingdoms of Alt Clut and Gododdin or Manaw Gododdin.

Taliesin's Marwnad Rhun (English: Elegy of Rhun) also tells of the war and Rhun's death in it. In his comprehensive discussion of the works by and attributed to Taliesin, John Morris-Jones notes that the particulars of the marwnad are everywhere consistent with the historical record and nowhere inconsistent, and likely a product of the 6th century, a view shared by notable skeptics such as Thomas Stephens.^[7]

The Venedotian Code says that the northern prince Elidyr Mwynfawr ap Gorwst Priodawr (English: Elidyr the Courteous, son of Gorwst Priodawr) had been slain at Aber Mewydus (now called 'Cadnant', or 'Battle Brook') in Arfon, not far from Rhun's llys (English: royal court) at Llanbeblig. Elidyr's powerful relatives in the North invaded Gwynedd in retaliation, burning Arfon in the process. The Northern host was led by Clydno Eiddin; Nudd the Generous, son of Senyllt; Mordaf the Generous, son of Serfan; and Rhydderch Hael, son of Tudwal Tudelyd.

These are all notable men of the era who are listed in the royal genealogies of the Bonedd Gwŷr y Gogledd, as is Elidyr Mwynfawr. According to one of the Triads of the Horses, Elidyr was also the husband of Rhun's sister Eurgain.^[8]

Rhun then assembled an army and proceeded to the banks of the Gweryd (the banks of the River Forth or the Firth of Forth, which William Forbes Skene says was still called the 'Weryd' in 1165)^[9] in the North. The final outcome is not given in the Venedotian Code, but Rhun and his army remained in the North for a considerable length of time.^[10] The outcome according to Taliesin's Marwnad Rhun is the death of Rhun ap Maelgwn in battle. He was succeeded by his son Beli ap Rhun as King of Gwynedd.

The reason why Elidyr was in Gwynedd and the circumstance of his death are not known, though it is certain from their actions that his northern relatives blamed someone in Gwynedd. There are later stories that add speculations, for example by asserting that Elidyr was contesting Rhun's succession to Maelgwn Gwynedd's throne,^[11] but these are nothing more than speculation.

Caerhun (meaning: Fort of Rhun) is the site of the 2nd century minor Roman fort of Canovium, situated along the Roman road between the larger Roman forts of Deva (at modern Chester) and Segontium (near modern Caernarfon). It is supposed to have been one of Rhun's strongholds, and while definitive evidence of this is lacking, it is circumstantially supported by archeological research and the antiquity of the name Caerhun.^[12][13] Furthermore, it guards an important crossing of the River Conwy at Tal-y-Cafn which leads to the pass at Bwlch-y-Ddeufaen,^[14] an entrance to Eryri (Snowdonia), the defensive heartland of the Kingdom of Gwynedd. Its military significance would certainly have been noticed by both defenders and potential aggressors.

The story of The Dream of Rhonabwy in the 12th century Red Book of Hergest is a prose literary tale where the main character travels to the time of King Arthur in a dream. There he sees the famous men from many historical eras. In a passage where 24 knights arrive to seek a truce with the famous Arthur, Arthur considers the request by assembling his counselors where "a tall, auburn, curly-headed man" was standing. Rhonabwy asks who he is, and is told that he is Rhun ap Maelgwn Gwynedd, a man who may join in counsel with anyone, because there was none in Britain better skilled in counsel than he.^[15]

Marwnad Rhun (English: Elegy of Rhun), once believed to be the work of Taliesin but no longer accepted as such, laments Rhun's death in battle during that War with the North.^[7]

Rhun appears in two of the medieval Welsh Triads, as one of the 'Fair Princes of the Isle of Britain',^[16] and as one of the 'Golden-banded Ones of the Isle of Britain'.^[17]

The Tale of Taliesin is a legendary story about Taliesin printed in the Mabinogion, and based in part on the forgeries of the Iolo Manuscripts by Iolo Morganwg.^[18] The story tells of events where Taliesin is placed in difficult or impossible situations but invariably overcomes all obstacles, usually through feats of magic. In one passage, Maelgwn Gwynedd sends his son Rhun on a mission to seduce the wife of Elffin ap Gwyddno. However, Elffin's court bard Taliesin knew of Maelgwn's plan because he was a seer, and arranged for a servant to replace his patron's wife, to the ultimate embarrassment of his patron's opponent Maelgwn.^[19]

One of the Triads mentions a certain Rhun ap Beli^[20][21] (English: Rhun son of Beli) who was famed for his military exploits. The name is repeated elsewhere in medieval poetry, such as in Hywel Foel's (fl. c. 1240 – 1300) awdl lamenting the capture and imprisonment of Owain ap Gruffudd, where he likens Owain to Rhun: "Who if free, like Rhun the son of Beli, Would not let Lloegria burn his borders".^[22] There is no confirming evidence that such a person existed, and it is contradicted by records such as the royal genealogies, which have Rhun as the father (not the son) of Beli. Scholars such as Thomas Stephens have concluded that this is a mistake,^[22] and that the intended person was someone else.

• Kings of Wales family trees