In medieval times, Craigmillar, other spellings include Cragmillar, Craigmillare, Cragmeloure, Cragmelor and Cragmulor, most probably derived its name from the Gaelic, craig moilard,
roughly translated, a high jutting rock upon a mound.
It is upon and around such a crag that the castle was subsequently built.
In 1137, David I gifted the lands of Craigmillar to the Church of the Holy Trinity of Dunfermline. His parents, Malcolm III and Margaret, had been married at the Church and his father, Malcolm Canmore, King of Scots, in 1093, was buried there. It was David who founded Dunfermline Abbey in 1128. At some point the lands of Craigmillar came into the possession of a John or William de Capella. ‘De Capella’ may simply have been a reference to the church. Entries by the Rev. Thomas Whyte in Archaeologica Scotica suggest that the lands had anciently belonged to the Craig-Millars and it was they who had gifted, in the 13th century, ‘certain lands and buildings to the church and monastery of Dunfermline’.
The lands of Craigmillar, in 1374, were granted to Sir Symon Preston to be held as an hereditary fiefdom by Robert II. Some records note the lands had been purchased from the previous tenant, William de Capella. Others documents note that they had been ‘surrendered’. It should also be remembered that in medieval Britain all lands were ultimately owned by the monarchy.
The oldest part of the castle is the tower. At least one reference accredits the building to Sir Symon Preston in 1365.