The name Excalibur ultimately derives from the Welsh Caledfwlch (and Breton Kaledvoulc'h, Middle Cornish Calesvol) which is a compound of caled "hard" and bwlch "breach, cleft". Caledfwlch appears in several early Welsh works, including the poem Preiddeu Annwfn (though it is not directly named - but only alluded to - here) and the prose tale Culhwch and Olwen, a work associated with the Mabinogion and written perhaps around 1100. The name was later used in Welsh adaptations of foreign material such as the Bruts (chronicles), which were based on Geoffrey of Monmouth.
It is often considered to be related to the phonetically similar Caladbolg, a sword borne by several figures from Irish mythology, although a borrowing of Caledfwlch from Irish Caladbolg has been considered unlikely by Rachel Bromwich and D. Simon Evans. They suggest instead that both names "may have similarly arisen at a very early date as generic names for a sword"; this sword then became exclusively the property of Arthur in the British tradition.
Geoffrey of Monmouth, in his Historia Regum Britanniae (The History of the Kings of Britain, c. 1136), Latinised the name of Arthur's sword as Caliburnus (potentially influenced by the Medieval Latin spelling calibs of Classical Latin chalybs, from Greek chályps "steel"). Most Celticists consider Geoffrey's Caliburnus to be derivative of a lost Old Welsh text in which bwlch had not yet been lenited to fwlch.
In Old French sources this then became Escalibor, Excalibor, and finally the familiar Excalibur. Geoffrey Gaimar, in his Old French L'Estoire des Engles (1134-1140), mentions Arthur and his sword: "this Constantine was the nephew of Arthur, who had the sword Caliburc" ("Cil Costentin, li niès Artur, Ki out l'espée Caliburc"). In Wace's Roman de Brut (c. 1150-1155), an Old French translation and versification of Geoffrey's Historia, the sword is called Calabrum, Callibourc, Chalabrun, and Calabrun (with alternate spellings such as Chalabrum, Calibore, Callibor, Caliborne, Calliborc, and Escaliborc, found in various manuscripts of the Brut).
In Chrétien de Troyes' late 12th-century Old French Perceval, Arthur's knight Gawain carries the sword Escalibor and it is stated, "for at his belt hung Escalibor, the finest sword that there was, which sliced through iron as through wood" ("Qu'il avoit cainte Escalibor, la meillor espee qui fust, qu'ele trenche fer come fust"). This statement was probably picked up by the author of the Estoire Merlin, or Vulgate Merlin, where the author (who was fond of fanciful folk etymologies) asserts that Escalibor "is a Hebrew name which means in French 'cuts iron, steel, and wood'" ("c'est non Ebrieu qui dist en franchois trenche fer & achier et fust"; note that the word for "steel" here, achier, also means "blade" or "sword" and comes from medieval Latin aciarium, a derivative of acies "sharp", so there is no direct connection with Latin chalybs in this etymology). It is from this fanciful etymological musing that Thomas Malory got the notion that Excalibur meant "cut steel" ("'the name of it,' said the lady, 'is Excalibur, that is as moche to say, as Cut stele'").