"Erat nomen gladio 'Crocea Mors' qua nullus eyadebat vivus qui eo vulnerabatur"
The sword was named 'Yellow Death' as none lived whom it wounded.
-Geoffrey of Monmouth

Note: This node is pseudo-historical at best, so please suspend your disbelief and enjoy a good tale instead of writing me angry /msgs pointing out that this is obviously a bunch of hooey. Thanks!

When Julius Caesar came to conquer Britain, he brought with him the legendary Crocea Mors, a golden sword forged by Vulcan and bestowed upon the Trojan prince Aeneas by his mother, Venus. Aeneas saw the sword fall from the sky, and as he grasped it, he heard a voice whisper, "With this, conquer." The sword was lost during the years of the Roman Republic but was found again by Caesar in his youth, proof indeed that the gods had chosen him to be emperor of the known world.

Cassibellaun, king of the Britons, met Caesar at the town of Dorobellum at the mouth of the Thames with his armies, commanded by his vassals and other "inferior" kings. It so happened that the king's brother Nennius of Canterbury, along with Androgeus of Trinovantum (the Latin name for London(1)), happened upon the legion Caesar himself was commanding. Nennius came to blows with Caesar, who raised his deadly blade to bring all of its might to bear on Nennius, hoping to fell his foe with a single mortal blow. Nennius' shield met the blade, which deflected onto his helmet. The force of Caesar's blow planted the blade into the helmet with such force that Caesar could not retrieve the blade, and he was forced to abandon it as his forces were routed. Nennius managed to pry the blade from his helmet (not to mention his head) and employed it against the Romans, hewing heads and arms left and right.

Fifteen days after the battle, Nennius died from the wound inflicted upon him by Crocea Mors. The sword was laid with him in his tomb. It lay there for 500 years until King Vortigern withdrew it from the tomb, commanding it to be pounded it into a foot high anvil of iron known as the Anvil of Vulcan, which was placed upon a great cube of stone in the middle of London's town square. Vortigern displayed the trophy of the ancient victory over the Romans to improve the morale of his people, who feared an invasion from the western Roman empire.

This is the point at which the stories of The Sword in the Stone and Excalibur begin to get a bit muddy - for it seems they may be the same sword. Crocea Mors, sitting untended in London's town square proved a tempting target for wandering passers-by, many of whom tried to pull it out. None succeeded, and one frustrated would-be sword thief carved, "(much treasure) to free from stone (of iron)," underneath the hilt - in Latin, "ex cal(ce)liber(ace)." It takes little imagination to find the Excaliber from this engraving. Geoffrey of Monmouth called it Calibernus - a name also not far from the engraving.

The sword sat in London square, forgotten as Britain sank into anarchy as rulership of the isles was left vacant following the departure of Theodoric "The Elder" (not "The Great," to whom the hardlink refers). As Britain descended into civil war, Bishop Bryce prayed for a sign from heaven to help end the fighting. A vision of Vortigern's war memorial appeared to him, and a voice spoke, saying, "Who so pulleth out Caesar's Sword from Vulcan's Anvil shall he King of Britons be; for God shall withhold it from everyone save from him whom He shall choose."

And the rest, as we know, is history.

1: This is a name given by Geoffrey of Monmouth. A quick reading of nodes both on him and the city's name indicate that it's entirely possible that no one actually called it "Trinovantum."
Dictionary of Phrase and Fable, E. Cobham Brewer
Age of Arthur , David Hughes
History of the Kings of Britain, Geoffrey of Monmouth