The embarrassment of the king's capture at Ainwick was the signal for the first revolt of his reign, in Galloway. It took three years for Nithsdale to be reoccupied and it was probably then that the royal castle at Dumfries was constructed. The problem of the south-west lingered on until 1186, when William was again at Dumfries. In 1179 the first attempt to subdue the north took place: a royal army with the King and his brother David at its head marched into the frontier land of Easter Ross, and established two new castles there. This, it is likely, was an expedition which aimed at the containment of the southward expansion of the influence of the earls of Orkney from Caithness into Ross. The next northern rising, in 1181, was potentially a far more serious threat, for it involved a macWilliam claim to the throne. It took seven years to quell, temporarily wrenched Ross out of control of the King of Scots and threatened disorder as far south as Gowrie. By 1187 the pretender, Donald, was dead and William was able to reclaim Inverness, but it took a further ten years for the northern frontier again to be pushed northwards into Ross.

The 1180s marked a prolonged and severe crisis, which saw two theatres of provincial revolt. Both were almost certainly protests against feudal colonisation as well as a threat to the dynasty itself. The crisis was weathered but the twin problems in the north remained. The potential for disruption by Harold Maddadson, Earl of both Caithness and Orkney, provoked royal expeditions to the north in 1197 and 1202 to neutralise this threat. Disaffection with the macMalcolm line persisted, breaking out in further macWilliam rebellions in Ross in 1211 and shortly after William's death in December 1214. No king of Scots before him had as formidable an apparatus of military power as William the Lion, but few kings needed it more.