Irish Gaels moved north and began to colonize the area sometime in the 4th or 5th Century. These people formed the Gaelic kingdom of Dal Riata. The golden age of Dal Riata is thought to be around near the beginning of the 7th Century and began a decline, with intermittent revivals occurring as late as the 9th Century.
Columba came to the Inner Hebrides in 563, founding a monastery on Iona and a number of other monasteries and retreats in the surrounding islands. The first written records of the islands began with the arrival of Columba.
The Hebrides began to come under Norse control and settlement already before the 9th century AD. The Norse control of the Hebrides was formalized in 1098 when Edgar of Scotland formally signed the islands over to 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 and devastating campaign earlier the same year, directed against the local Norwegian leaders of the various islands after they had begun paying homage to Edgar as their overlord. 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. The Outer Hebrides would remain under the Kingdom of Mann and the Isles while the Inner Hebrides broke out under Somerled, the Norse-Gaelic kinsman of both Lulach and the Manx royal house.
After his victory of 1156 Somerled went on to two years later seize control over the Isle of Man itself and become the last King of the Isle of Man and the Isles to rule over all the islands the kingdom had once included. After Somerled's death in 1164 the rulers of Mann would no longer be in control of the Inner Hebrides.
The Lord of the Isles would continue to rule the Inner Hebrides as well as part of the Western Highlands as a subject of the King of Scots until John MacDonald, fourth Lord of the Isles, squandered the family's power away. Through a secret treaty with Edward IV of England in 1462, he planned to make himself more or less an independent ruler. When James III of Scotland found out about the treaty in 1475, he forfeited MacDonald's lands. Some were restored for a promise of good behaviour, but MacDonald was unable to control his son who defeated him at the Battle of Bloody Bay (Mull, 1481) and his nephew whose rebellion in 1493 provoked an exasperated James IV to forfeit the lands for the last time in 1493. MacDonald died in 1503.
The Islands of the Clyde are sometimes mislocated in the Southern Hebrides. Technically they are not part of the archipelago.