The origin of Arthur in literature is hazy; beyond a certain point, legend and 'history' mingle and are practically indistinguishable. Stories of Arthur taken from roughly contemporary 5th and 6th Century sources are typically presented as fact, even if they seem to be based on tall tales or hearsay. However, they are not quite the fantastic world of knights, magic and questing, but describe a more brutal world of military campaigns and warlords fighting over the strife-riven islands of Britain. By the 7th Century, Arthur had assumed the status of a peerless chieftain, mighty beyond comparison, as poems described warriors whose deeds were impressive but they were still 'no Arthur'.
Arthur's first major mention as a fabled king in literature appears in a collection of Medieval Welsh tales known as the Mabinogion, which was the title given to them by Lady Charlotte Guest who translated them into English in the mid-19th Century. These are to be found in their most complete form in the 14th Century manuscript known as the Red Book of Hergest. The tales are thought to date from the songs of a much earlier period, when the bards of both the Breton and Gallic peoples shared common legends and passed down their myths through speech. The rough dates for the composition of these tales are fiercely contested by historians, who have suggested they were written anywhere between the mid-11th Century and 1250 AD.
The Mabinogion comprises four main tales of Welsh myth, none of which mention Arthur. However, some of the minor strands bear many similarities with medieval French courtly literature, and there is explicit mention of Arthur and many of the common Arthurian motifs such as quests, Black Knights and damsels in distress, while also detailing extremely pagan ideas like shapeshifting, bards and magic cauldrons.
It is unsurprising that Arthur didn't become a greater literary figure earlier, as he was a Briton warlord fighting the Saxon invaders, who eventually became the dominant race in Britain and so obviously pruned anti-Saxon legends from the British culture. It wasn't until the Normans conquered and subjugated the Anglo-Saxons from 1066 onwards that Arthur became a celebrated mythic figure once again.
Fighting against the Saxons also meant that races descended from the Britons such as the Welsh hailed Arthur as a hero, a defender of British soil, and thus their poetic patronage of the Arthurian legends ensured that the tales survived the Dark Ages. Moreover, they started to be given fantastic elements in keeping with other Celtic folklore, and thus turn from truth to story to legend.
The Historia Regum Britanniæ
This was a work written by Geoffrey of Monmouth in the 12th Century which chronicled the lives of past kings of Britain, and by doing so legitimised and praised the current incumbent by association with such legendary figures. King Arthur is but one of these figures, and in telling his story, Geoffrey introduces several of the key themes of the mythos. The Historia is the earliest surviving text which mentions both Uther Pendragon, Arthur's father, and Merlin. These elements were crucial in establishing the romantic nature of the legend, as well as the fantastic; the concepts of a riven kingdom, a fated king-making and a mystical mentor are still key parts of the story's glamour even today.
Because this work purported to be a serious chronicle, it meant that future authors and poets could use it as a basis for their own endeavours. Despite the fact that, according to the Historia, the mythical King Brutus had to win back the island from a race of giants when he landed after fleeing the Trojan War, these subsequent writers and bards considered it such a touchstone because there weren't really any other historical records, and so for all intents and purposes, Arthur had been real, as had Merlin.