He was not, though, a national king in the sense that we understand the term, as under the Gaelic system kings were elected from the derbfine, a group made up of those whose great-grandfathers had been kings. The chosen successor, supposedly the fittest to rule, was known as the tanist. By the eleventh century, however, Scottish kings had become familiar with the principle of heredity, and were often tempted to bend the rules of tanistry. Thus, the childless Malcolm secured the succession of his grandson Duncan by murdering a potential rival tanist. Duncan, in turn, was killed by Macbeth in 1040. Macbeth was not, therefore, the villain of Shakespeare's imagination, but simply an ambitious Scot of royal blood acting in a relatively conventional way.

The victory over Macbeth in 1057 of Malcolm III, known as Canmore ('Bighead'), marked the beginning of a period of fundamental change in Scottish society. Having avenged his father Duncan, Malcolm III, who had spent the previous 17 years at the English court, sought to apply to Scotland a range of ideas he had brought back with him. He and his heirs established a secure dynasty based on succession through the male line and introduced feudalism into Scotland, a system that was diametrically opposed to the Gaelic system, which rested on blood ties: the followers of a Gaelic king were his kindred, whereas the followers of a feudal king were vassals bought with land. The Canmores successfully feudalized much of southern and eastern Scotland by making grants to their Norman, Breton and Flemish followers but, beyond that, traditional clan-based forms of social relations persisted.

The Canmores, independent of the local nobility, who remained a military threat, also began to reform the Church. This development started with the efforts of Margaret, Malcolm III's English wife, who brought Scottish religious practices into line with those of the rest of Europe and was eventually canonized. David I continued the process by importing monks to found a series of monasteries, principally along the border at Kelso, Melrose, Jedburgh and Dryburgh. By 1200 the entire country was covered by a network of eleven bishoprics, although church organization remained weak within the Highlands. Similarly, the dynasty founded a series of royal burghs, towns such as Edinburgh, Stirling and Berwick, and bestowed upon them charters recognizing them as centres of trade. The charters usually granted a measure of self-government, vested in the town corporation or guild, and the monarchy hoped this liberality would both encourage loyalty and increase the prosperity of the kingdom. Scotland's Gaelic-speaking clans had little influence within the burghs, and, by 1550, Scots - a northern version of Anglo-Saxon - had become the main language throughout the Lowlands.

The policies of the Canmores laid the basis for a cultural rift in Scotland between the Highland and Lowland communities. Before that became an issue, however, the Scots had to face a major threat from the south. In 1286 Alexander III died, and a hotly disputed succession gave Edward I, King of England, an opportunity to subjugate Scotland. In 1291 Edward presided over a conference where the rival claimants to the Scottish throne presented their cases. Edward chose John Balliol in preference to Robert the Bruce, his main rival; he also obliged Balliol to pay him homage, thus turning Scotland into a vassal kingdom. Bruce refused to accept the decision, thereby continuing the conflict, and in 1295 Balliol renounced his allegiance to Edward and sided with France - the beginning of what is known as the 'Auld Alliance'. In the conflict that followed, the Bruce family sided with the English, Balliol was defeated and imprisoned, and Edward seized control of almost all of Scotland.

Edward had shown little mercy during his conquest of Scotland - he had, for example, had most of the population of Berwick massacred - and his cruelty seems to have provoked a truly national resistance. This focused on William Wallace, a man of relatively lowly origins who raised an army of peasants, lesser knights and townsmen that was fundamentally different to the armies raised by the nobility. Figures like Balliol, holding lands in England, France and Scotland, were part of an international aristocracy for whom warfare was merely the means by which they struggled for power. Wallace, by contrast, led proto-nationalist forces determined to expel the English from their country. Probably for that very reason Wallace never received the support of the nobility and, after a bitter ten-year campaign, he was betrayed and executed in London in 1305.

With Wallace out of the way, feudal intrigue resumed. In 1306 Robert the Bruce, the erstwhile ally of the English, defied Edward and had himself crowned king of Scotland. Edward died the following year, but the unrest dragged on until 1314, when Bruce decisively defeated a huge English army under Edward II at the battle of Bannockburn. At last Bruce was firmly in control of his kingdom, and in 1320 the Scots asserted their right to independence in a successful petition to the pope, now known as the Declaration of Arbroath.

In the years following Bruce's death in 1329, the Scottish monarchy gradually declined in influence. The last of the Bruce dynasty died in 1371, to be succeeded by the 'Stewards', hence Stewarts, but thereafter a succession of Scottish rulers, culminating with James VI in 1567, came to the throne when still children. The power vacuum was filled by the nobility, whose key members exercised control as Scotland's regents while carving out territories where they ruled with the power, if not the title, of kings. At the close of the fifteenth century, the Douglas family alone controlled Galloway, Lothian, Stirlingshire, Clydesdale and Annandale. The more vigorous monarchs of the period, notably James I, did their best to curb the power of such dynasties, but their efforts were usually nullified at the next regency. James IV, the most talented of the early Stewarts, might have restored the authority of the crown, but his invasion of England ended in a terrible defeat for the Scots - and his own death - at the battle of Flodden Field.

The reign of Mary, Queen of Scots typified the problems of the Scottish monarchy. Mary came to the throne when just one week old, and immediately caught the attention of the English king, Henry VIII, who sought, first by persuasion and then by military might, to secure her hand in marriage for his five-year-old son, Edward. Beginning in 1544, the English launched a series of devastating attacks on Scotland, an episode Sir Walter Scott later called the 'Rough Wooing', until, in the face of another English invasion in 1548, the Scots - or at least those not supporting Henry - turned to the 'Auld Alliance'. The French king proposed marriage between Mary and the Dauphin Francis, promising in return military assistance against the English. The six-year-old queen sailed for France in 1548, leaving her loyal nobles and their French allies in control, and her husband succeeded to the French throne in 1559. When she returned 13 years later, following the death of Francis, she had to pick her way through the rival ambitions of her nobility and deal with something entirely new - the religious Reformation.