These first inhabitants were hunter-gatherers, whose heaps of animal bones and shells have been excavated, amongst other places, in the caves along the coast near East Wemyss in Fife. Around 4500 BC, Neolithic farming peoples from the European mainland began moving into Scotland. To provide themselves with land for their cereal crops and grazing for their livestock, they cleared large areas of upland forest, usually by fire, and in the process created the characteristic moorland landscapes of much of modern Scotland. These early farmers established permanent settlements, some of which, like the well-preserved village of Skara Brae on Orkney, were near the sea, enabling them to supplement their diet by fishing and develop their skills as boat-builders. The Neolithic settlements were not as isolated as was once imagined: geological evidence has, for instance, revealed that the stone used to make axe-heads found in the Hebrides was quarried in Northern Ireland.

'Scotland's mysterious stone circles were a massive commitment in terms of time and energy, with many of the stones carried from miles away'

Settlement spurred the development of more complex forms of religious belief. The Neolithic peoples built large chambered burial mounds or cairns, such as Maes Howe in Orkney. This reverence for human remains suggests a belief in some form of afterlife, a concept that the next wave of settlers, the Beaker people, certainly believed in. They placed pottery beakers filled with drink in the tombs of their dead to assist the passage of the deceased on their journey to, or their stay in, the next world. The Beaker people also built the mysterious stone circles, 30 of which have been discovered in Scotland. Such monuments were a massive commitment in terms of time and energy, with many of the stones carried from miles away, just as they were at Stonehenge in England, the most famous stone circle of all. One of the best-known Scottish circles is that of Callanish on the Isle of Lewis, where a dramatic series of monoliths (single standing stones) form avenues leading towards a circle made up of thirteen standing stones. The exact function of the circles is still unknown, but many of the stones are aligned with the position of the sun at certain points in its annual cycle, suggesting that the monuments are related to the changing of the seasons.

The Beaker people also brought the Bronze Age to Scotland. Bronze, an alloy of copper and tin, was stronger and more flexible than its predecessor, flint, which had long been used for axe-heads and knives. New materials led directly to the development of more effective weapons, and the sword and the shield made their first appearance around 1000 BC. Agricultural needs plus new weaponry added up to a state of endemic warfare as villagers raided their neighbours to steal livestock and grain. The Bronze Age peoples responded to the danger by developing a range of defences, among them the spectacular hillforts, great earthwork defences, many of which are thought to have been occupied from around 1000 BC and remained in use throughout the Iron Age, sometimes far longer. Less spectacular but equally practical were the crannogs, smaller settlements built on artificial islands constructed of logs, earth, stones and brush, such as Cherry Island in Loch Ness.

Conflict in Scotland intensified in the first millennium BC as successive waves of Celtic settlers, arriving from the south, increased competition for land. Around 400 BC, the Celts brought the technology of iron with them and, as Winston Churchill put it, 'Men armed with iron entered Britain and killed the men of bronze'. These fractious times witnessed the construction of hundreds of brochs or fortified towers. Concentrated along the Atlantic coast and in the northern and western isles, the brochs were dry-stone fortifications (that is, built without mortar or cement) often over 40ft in height. Some historians claim they provided protection for small coastal settlements from the attentions of Roman slave traders. Much the best-preserved broch is on the Shetland island of Mousa; its double walls rise to about 40ft, only a little short of their original height. The Celts continued to migrate north almost up until Julius Caesar's first incursion into Britain in 55 BC.

At the end of the prehistoric period, immediately prior to the arrival of the Romans, Scotland was divided among a number of warring Iron Age tribes, who, apart from the raiding, were preoccupied with wresting a living from the land, growing barley and oats, rearing sheep, hunting deer and fishing for salmon. The Romans were to write these people into history under the collective name Picti, or Picts, meaning painted people, after their body tattoos.