The first king named as rí Alban (King of Alba) was Donald II who died in 900. Before that the title seems to have been King of the Picts or King of Fortriu. Constantine II followed him and reigned for nearly half a century. When he lost the battle at Brunanburh, he joined the Culdee monks at St. Andrews and tradition claims he and bishop Ceallach of St Andrews, brought the Catholic Church into conformity with that of the larger Gaelic world.
The period between the accession of Malcolm I (Maol Caluim Mac Domhnuill) and Malcolm II (Maol Caluim Mac Cionaodha) was marked by good relations with the English. When King Edmund of England invaded cumbra land (Old English for Strathclyde or Cumbria or both) in 945, he then handed the province over to king Malcolm I on condition of a permanent alliance. During the reign of King Indulf (Idulb mac Causantín, 954–62), the fortress called oppidum Eden, i.e. almost certainly Edinburgh, was captured.
It marked the first foothold in Lothian. The reign of Malcolm II saw the Scoto-Pictish kingdom of Fortriu incorporated into Alba. He defeated the Northumbrians at the Battle of Carham in 1018. In the same year, King Owain died, leaving his kingdom of Strathclyde to his overlord Malcolm. A meeting of Malcolm with King Canute of Denmark and England in 1031 secured these conquests. Some say that Malcolm accepted Canute as his overlord, others do not. Lothian was not incorporated into Scotland until the Wars of independence.