When
Sweyn II invaded
Northern England in 1069, Waltheof and
Edgar Aetheling joined
the Danes and took part in the attack on
York. He would again make a fresh submission to William after the departure of the invaders in 1070. He was restored to his earldom, and went on to marry William's niece,
Judith of Lens. In 1071, he was appointed
Earl of Northampton. The
Domesday Book of 1086 mentions Waltheof ("
Walleff"): "'In
Hallam ["
Halun"], one manor with its sixteen hamlets, there are twenty-nine
carucates [~14 km²] to be taxed. There Earl Waltheof had an "Aula" [hall or court]. There may have been about twenty ploughs. This land Roger de Busli holds of the Countess Judith" (Hallam, or
Hallamshire, is now part of the city of
Sheffield). In 1072, William expelled
Gospatric from the earldom of Northumbria. Gospatric was Waltheof's cousin and had taken part in the attack on York with him, but like Waltheof, had been pardoned by William. Gospatric fled into exile and William appointed Waltheof as the new earl. Construction of
Durham Castle began under Waltheof in 1072 after receiving orders to commence this project from William. The castle would be significantly expanded by Bishop
Walcher and his successors in later years. Waltheof had many enemies in the north. Amongst them was the family of
Thurbrand the Hold; Thurbrand had killed Waltheof's great-grandfather,
Uhtred the Bold, starting a long-running blood-feud that had resulted in the deaths of many members of both families. In 1074, Waltheof made a decisive move by sending his retainers to ambush his rivals, succeeding in killing the two eldest of four brothers. ==Second revolt and execution==