Meantime, King Harold's mother, Gytha encouraged the people of Devon to rise up and William had major problems subduing them, especially in retaking the city of Exeter. At the same time, the other main claimant to the English throne, Edgar Ætheling, had escaped the Norman king's clutches and gone to Scotland with his family and a large number of important men. The south was also restive and later in the year, the men of Dover invited Eustace of Boulogne to help them in their insurrection. This uprising was soon put down, and without the presence of King William himself. The people of the north were also chafing under Norman rule. William advanced upon them with his army, burning and laying waste as he went, The men of Northumberland lacked the confidence to take part in a battle and either submitted or fled into Scotland to join the other refugees there.
In the autumn two of King Harold's sons, who had gone to the Norse east coast of Ireland, came and raided the west country, where the Celtic Cornishmen joined them in arms. They plundered and ravished the countryside to such an extent that eventually even the English lost patience and joined with local Norman garrisons to expel them.
In the following year of 1068, King William appointed a certain Robert de Comines, Earl of Northumberland, without asking the locals if they would accept him instead of the English Earl Morkar. The result was that the men of Northumberland massacred Robert and 900 of his men whilst they were staying in the city of Durham. Edgar Ætheling took advantage of this and came from Scotland and received the men of Northumberland at York. William moved up fast from the south and surprised the Northumbrians. Hundreds were slain and the city torched.
1069 and Harold's sons were back, raiding the west country again. Unfortunately for them they met defeat at the hands of Earl Brian of Penthievre, and fled back to Ireland. At the same time Edric the Wild and his Welsh allies had broken out from their Marcher hills and took Shrewsbury before moving on to Chester. William had to leave them to their own devices as he had his hand's full dealing with an uprising in Northumberland lead by Morkar and his brother Edwin supported by the Danish king, Swein Esthrithson, who also had a claim to the English throne. Fighting alongside them were the Earls and Gospatrick, together with Edgar Ætheling. The Normans in York were slaughtered, with Earl Waltheof's exploit of slaying a hundred Frenchmen with his long-axe as they tried to escape through a gate, ending up in heroic verse. William moved north again laying waste as he went. The Danes took to their ships and commenced raiding the east coast, seeking assistance from their relations in the Danelaw part of England, which included the marshy wetlands of the Fens, where other trouble was brewing. William left part of his army to watch them whilst he crossed the Pennine hills to face the threat posed by Edric and the Welsh princes, who now had a formidable army bolstered by the men of Cheshire and Staffordshire. William rode with his men and joined Earl Brian, who had marched up from the west country after beating Harold's sons. Edric became wary and withdrew to the hills with his Herefordshire and Shropshire men. The Welsh, with the remaining English, marched on and were defeated at the battle of Stafford. William then devastated the land about and laid it waste. A further revolt in the west country, that seemed to be aimed at individual Normans, fizzled out in the face of forces drawn from London and the south east and through internal dissent amongst the insurgents.
William now dealt with the Northumberland problem, a problem that had grown with the stepping up of revolt in the Fens lead by a local landholder, . After a hard march north along a route determined by violent resistance, broken bridges and swollen rivers, William took and re-entered York without a fight. The Danes had fled and the men of Northumberland, dispirited by William's ability to advance despite the hazards set before him by both nature and English, fled into the hills, pursued by King William's men. With grim determination, William's army set about destroying homes and crops, and extinguishing all human and animal life from the Humber to the Wash. Those that avoided violent death, died from exposure or starvation.
The blood letting didn't stop William from celebrating Christmas at York, complete with a feast served on silver plate especially brought up from Winchester. Christmas over, William chased the men of Tees around the Cleveland hills. William's harrowing of the north had its effect on the leaders of the northern rebellion, as Waltheof and Gospatrick both came to an accommodation with him. The king made his way back to York in atrocious conditions, seeking bands of Englishmen as he went, and suffering heavy losses of men in the process. Here he re-erected the castles the Anglo-Norse had burned down and re-garrisoned them. He was now able to turn his attention to Chester, which was defiantly refusing to recognise him. Chester was at the northern extremity of the Welsh Marches and at the same time offered access to the Norse based in Ireland, should they decide to help their relations living in Cumberland.
In January 1070, a Norman army set off across the Pennines in bad weather through land that offered them no sustenance as they themselves had laid it waste. William's army suffered badly in the hills to both weather and English attacks. The men, who were mainly mercenaries from the northern provinces of France, mutinied, so he abandoned them to their fate. With a reduced force consisting of only Normans, he arrived at Chester, and it submitted without a fight. He then busied himself building castles to hold the north down. He also spent money on buying the Danes, under their leader, Jarl Osbjorn, off with a large Danegeld.
The revolt in the Fens, lead by , had been strengthened by refugees from the harrowing of Northumberland, including Earl Morkar. At the same time it had been weakened by Osbjorn taking the bribe. However, whilst his brother, Jarl Osbjorn, and his fleet had been bought off, King Swein of Denmark and his new fleet hadn't! What happened during the years 1070 and 1071 is as much legend as recorded fact. We know that William made at least two unsuccessful attempts, either in person, or through a lieutenant, to take the where Hereward and his forces were based. We also know that Hereward kept his Danish allies paid by allowing them to sack Peterborough and its Cathedral, now controlled by a Norman Bishop. What we do not know are the exact happenings, or the sequence of events. Eventually Swein, perhaps seeing himself in a no win situation, allowed himself to be bought off. Later Ely was taken by the Normans after local monks betrayed secret causeways through the Fens that would allow an army access to the Isle. Although Ely fell in 1071, Hereward escaped and, with a band of followers, remained a thorn in King William's side for many years to come.
1072 and the trouble came from the Scots with their numbers swelled by many English, including Edgar Ætheling. William took an army across the border and confronted Malcolm King of Scots at Abernethy. Malcolm accepted the inevitable and made peace.