Construction of the bridge was begun in the late 13th century by Richard Cementarius, although its completion was not until 1320 at the time of the Scottish War of Independence.

For five centuries possession of the bridge was the only way to move large armies quickly along the eastern coast of Aberdeenshire.

The text below is taken from the notes of a public talk History of the Brig o'Balgownie given by Dr. Christopher P. Croly from the Archaeological Unit at Aberdeen City Council.

[1] However the very earliest references to the barony, or settlement, of Balgownie invariably have the word as Palgoueny, or Polgowny, or a number of minor variants, generally starting with Pol.

[2] There are two possible suggestions for the second part, some say that gabhainn, genitive of gabhann, means a "of a cattle-fold"[3] whilst others have asserted that it derives from gobhainn which indicates a blacksmith, or just a smith.

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.

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.

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.

"[7] Thus the two earliest versions of this story both put the onus for building the bridge on Robert the Bruce, and neither mention involvement by Bishop Cheyne.