The familiar story is that the stone bridge was commissioned by either Bishop Henry Cheyne or Robert the Bruce, or indeed was begun by the former and completed by the latter, and that the work was done by Richard Cementarius. It is said that Cheyne started the work but fled Bruce's troops, and then Bruce finished the work later on. However, the earliest written version of the origins of the bridge is slightly at odds with later ones. The first written history of the bridge was by Sir Alexander Hay, in a charter of 1605. In the charter he wrote that the bridge "was built by command, and at the expense of, the deceased most invincible prince, Robert Bruce, king of the Kingdom of Scotland." This account only contains one element of what becomes a fairly consistent story. Parson Gordon was the first to record a fuller version of the story some sixty years after Hay. He wrote: "No man can certainly tell who builded the Bridge of Done. The commone and most probable reporte is that the renouned Prince Robert Bruisse, King of Scotland, at such tyme as he banished B. Henrie Cheyne from his sea, and drave him out of Scotland beside, did command for to sequester the bishops yeerlie revenue to be imployed towards pious uses, and that this bridge (which is lyke to be true) was builted with a part of that revenue."