Tradition holds that the Kingdom of Scotland was formed in 843 CE when Kenneth MacAlpin conquered the Picts and established the Kingdom of Alba. The veracity of this account has been disputed by modern scholars, as much of Kenneth's reputation rests on myth. Nonetheless, a rough entity called the "Kingdom of Alba", which was based on a merger of several Pictish and Gaelic entities did exist by 900, and was firmly established during 10th Century. The name "Scotia" that had been applied to the center of these small monarchies, and by the 11th Century at the latest, the kings of Alba had come to call themselves the kings of Scots.
In 1603, James VI, who'd reigned over Scotland since 1567, ascended to the English throne. While this created a personal union, each remained a separate country. In the mid 17th century, English dominance over Scotland was tightened by Oliver Cromwell, who ruled these countries as monarch without a crown. In 1707, the Acts of Union created a single state and crown. The title "King/Queen of the Scots" fell into disuse; however, the new monarchy of Great Britain and Ireland, which was succeeded by the monarchy of the United Kingdom of Great Britain and Ireland in 1800, continues on as the head of state of Scotland.
Turtledove has written little or nothing about Scotland's history prior to Mary I of Scotland, who died not long before the union of the crowns, nor have any of his timelines explored a Britain where the union was prevented (In High Places has one, but names no monarchs), so most of the monarchs listed here were also monarchs of England, the only exception (as of October 2015) being Mary herself.