The Hebrides were settled early on in the settlement of the British Isles, perhaps as early as the Mesolithic era, around 8500-8250 BC, after the climatic conditions improved enough to sustain human settlement. There are examples of structures possibly dating from up to 3000 BC, the finest example being the standing stones at Callanish. Little is known of the people who settled in the Hebrides but they were likely of the same Celtic stock that had settled in the rest of Scotland. Settlements at Northton, Harris, have both Beaker & Neolithic dwelling houses, the oldest in the Western Isles, attesting to the settlement. The earliest written mention of the Outer Hebrides was by the Greek historian Diodorus Siculus in 55 BC. He wrote that there was an island called Hyperborea (which means "Far to the North") where a round temple stood from which the moon appeared only a little distance above the earth every 19 years, an apparent reference to the stone circle at Callanish. Other ancient writers such as Pliny the Elder, the Egyptian astronomer Ptolemy, and Solinus (3rd Century AD) all seem to mention the Hebrides, attesting to some contact of the peoples there to the Roman world.
Norse control of the Hebrides was formalised in 1098 when Edgar of Scotland recognised the claim of Magnus III of Norway. The Scottish acceptance of Magnus III as King of the Isles came after the Norwegian king had conquered the Orkney Islands, the Hebrides and the Isle of Man in a swift campaign earlier the same year, directed against the local Norwegian leaders of the various islands. By capturing the islands Magnus III subdued the Norsemen who had seized the islands centuries earlier and imposed a more direct royal control. The Norwegian control of both the Inner and Outer Hebrides would see almost constant warfare until being ultimately resolved by the partitioning of the Western Isles in 1156. Although the Inner Hebrides, from 1156, known as the Kingdom of the Hebrides, was still nominally under the sovereignty of Norway, the leaders were Scottish in language and culture rather than Norse.