I happily/regrefully inform you that there is no straightforward answer here. I'll try to be concise (ETA: in retrospect, I failed).

The earliest accepted date for a text is the Historia brittonum from the early 9th century. It doesn't give us much for Arthur himself, just that he is a "leader of wars" (dux bellorum) and recounts a list of battles in which he fought. This chronicle/history work is attributed to a monk named Nennius, although his authorship is very much in contention. The earliest surviving manuscript of the Historia brittonum is from the 11th century.

The earliest dateable story-text in which Arthur plays a role, albeit as a side character, is the Welsh Culhwch and Olwen. This fantastical legend-type poem is found in manuscripts from the 14th and 15th centuries, but scholars agree the language places its composition in the 11th century. We don't know who originally wrote this story/wrote it down.

The earliest narrative of what we think of as the "plot" of Arthur's rise and fall is Geoffrey of Monmouth's Historia Regum Britanniae. This text is from the early-mid 12th century.

Two of the most important characteristics of the modern idea of "King Arthur"--Lancelot and Guinevere on one hand, the Holy Grail on the other--come from the romances of Chretien de Troyes (which scholars are beginning to consider may be a pseudonym) in the second half of the twelfth century.

In the first half of the century, two sets of linked texts known as the Vulgate Cycle (or Lancelot-Grail Cycle to denote the massive shadow that the character of Lancelot casts in comparison to other full narratives) and Post-Vulgate Cycle "put together" the whole shebang--the Grail's arrival in England, Merlin's half-demonic ancestry, strange women lying in ponds distributing swords as the basis for a system of government, Grail-questing, Arthur's death and promised return. It's a little odd to say "put together" because these are still multiple texts by multiple authors, some with VERY different agendas, but the manuscript evidence tells us that medieval people associated them as parts of a whole.

The most common single basis for modern (19th century onwards) interpretations of King Arthur Et Alia is Thomas Malory's Le Morte d'Arthur, from the late 15th century.

BUT.

There are two big questions.

The first is an unconnected group of Welsh poems whose manuscripts mostly date from the 13th century or later, hardly unusual. These often claim to be written by 6th-century poets, also not unusual, and also not a claim that any Arthuriana scholar takes seriously. However, there have been attempts to date some of them to as early as the 7th or 8th centuries, although, well, they tend to be considered more in the "an attempt was made" category. 9th or 10th century has generally had better traction.

Second, Geoffrey of Monmouth (early 12th century) says that he has learned much about his subjects from an old book. Some scholars want this to be the Historia brittonum, which seems way too coincidental; some scholars identify this as a fairly typical deployment of the "in an old book" trope, which is completely plausible and usually considered the most likely; and some do maintain that there is a now-lost older narrative account of Arthur.

I leave it to you to decide from these options what qualifies as "the oldest written story of King Arthur."