Excalibur, the sword of King Arthur is first mentioned in Geoffrey of Monmouth's The History of the Kings of Britain. According to this account, King Arthur gets a sword called "Caliburn," which was made on the Isle of Avalon. Later legends have the sword being returned to the Lady of the Lake on the mortal wounding of King Arthur at Camlann. Legend is vague as to the location of the Lake that features in the Excalibur story, but possible candidates for the Excalibur Lake are here.
It was not until Robert de Boron wrote Merlin (c. 1200) that the author introduced the story of the young King Arthur drawing the sword Excalibur from a rock. Hence proving that Arthur was rightful king of Britain, the true heir of Uther Pendragon.
The appear therefore that King Arthur had two swords. The sword drawn from the rock is different from the one given to Arthur by the Lady of the Lake. The lake sword and the rock sword. Excalibur is certainly the lake sword.
There could be a translation problem giving rise to the sword being said to be drawn from the stone. The Latin word for stone is saxo; the Germanic invaders were Saxon. It is possible that the original story had King Arthur killing a Saxon leader and pulling his sword from the dead body, and that that in copying (everything was hand copied in those days), a scribe might have missed the last letter of Saxon. In the legend of King Arthur, all things are possible.
In the Post-Vulgate Merlin, Excalibur was taken from a hand rising from a lake. In this Post-Vulgate version, the blade of Excalibur could cut through everything and its sheath made the wearer invincible.
Full references to more about Excalibur at the Rochester site on King Arthur and Excalibur.
The Legend of King Arthur