The grand strategy portion of the game is played on a large campaign map of Britannia.

In the prologue, the player takes the role of Septimus Sulla, heir to one of the Roman families that ruled in Britannia south of Hadrian's Wall.

In the main campaign, the player takes over the role of William Pendragon, son of the once and future King Arthur.

Arthur lies mortally stricken by a magical curse and several of the figures of Arthurian legend are missing when William steps up to unite the provinces that once made up Arthur's kingdom, fight back the Fomorians unleashed by the Witch Queen Morgawse from the Orkney Islands and find a way to heal his father.

As in the previous game, other heroes join the army of William and, eventually, a second army led by the sorceress Morgana Le Fay becomes available as William allows her to search in the name of King Arthur for her mentor Merlin, who was kidnapped by the enchantress Lady Nimue.