Matilda was born around 1080 in Dunfermline, the daughter of Malcolm III of Scotland and Saint Margaret. She was christened (baptised) Edith, and Robert Curthose stood as godfather at the ceremony. Queen Matilda, the consort of William the Conqueror, was also present at the baptismal font and was her godmother. Baby Matilda pulled at Queen Matilda's headress, which was seen as an omen that the younger Matilda would be queen one day.

The Life Of St Margaret, Queen Of Scotland was later written for Matilda by Turgot of Durham. It refers to Matilda's childhood and her relationship with her mother. In it, Margaret is described as a strict but loving mother. She did not spare the rod when it came to raising her children in virtue, which Tugot supposed was the reason for the good behaviour Matilda and her siblings displayed. Margaret also stressed the importance of piety.

When she was about six years old, Matilda of Scotland (or Edith as she was then probably still called) and her sister Mary were sent to Romsey Abbey, near Southampton, where their aunt Cristina was abbess. During her stay at Romsey and, some time before 1093, at Wilton Abbey, both institutions known for learning,[4] the Scottish princess was much sought-after as a bride; refusing proposals from William de Warenne, 2nd Earl of Surrey, and Alan Rufus, Lord of Richmond. Hériman of Tournai even claims that William II Rufus considered marrying her.

She had left the monastery by 1093, when Anselm, Archbishop of Canterbury, wrote to the Bishop of Salisbury ordering that the daughter of the King of Scotland be returned to the monastery that she had left.