Revolt of the Earls
In August 1072, King William invaded Scotland. He doesn't appear to have met with any significant resistance, and he received the submission of, the Scots' king, Malcolm Canmore at Abernethy (on the south bank of the Tay).
"William returning thence [from Scotland] deprived Cospatric [Gospatric] of the dignity of his earldom, charging him with having afforded counsel and aid to those who had murdered the earl [Robert de Comines] and his men at Durham, although he had not been present in person; and that he had been on the side of the enemy when the Normans were slain at York."
Symeon of Durham 'Historia Regum'
Symeon notes that Gospatric fled to King Malcolm. After a sojourn in Flanders, he returned to Scotland, and Malcolm: "... bestowed upon him Dunbar, with the lands adjacent in Lothian, that out of these he might provide for himself and his friends until more prosperous times should come."  To which statement Roger of Hoveden adds: "But not long after this, being reduced to extreme infirmity, he sent for Aldwin and Turgot, the monks, who at this time were living at Meilros [Melrose], in poverty and contrite in spirit for the sake of Christ, and ended his life with a full confession of his sins, and great lamentations and penitence, at Ubbanford, which is also called Northam, and was buried in the porch of the church there. He gave them two fair dorsals, that, in whatever place they might chance to take rest, they should set them up there in remembrance of him. These are still preserved in the church at Durham."
"Cospatric being cast down from his dignity, Waltheov [Waltheof] was raised to the earldom, which was his right by his father's and mother's descent [Note] ... At that time (namely, when the king had returned from Scotland) he built a castle in Durham, where the bishop might keep himself and his people safe from the attacks of assailants....
Walcher ("a clerk of the church of Liège") was now bishop of Durham.  Add.10
.... Bishop Walcher and earl Waltheov were very friendly and accommodating to each other; so that he, sitting together with the bishop in the synod of priests, humbly and obediently carried out whatever the bishop decreed for the reformation of Christianity in his earldom."
Symeon of Durham 'Historia Regum'
The charges made against Gospatric might be thought to apply just as well to Waltheof. However, Waltheof was clearly a favourite of King William. Orderic Vitalis calls Waltheof "one of the greatest of the English", and notes that the king "married him to his own niece Judith to strengthen the bonds of friendship between them". The marriage may well have already taken place when Waltheof was given Gospatric's earldom.
In fact, Orderic never mentions Waltheof's acquisition of the north-Northumbrian earldom. He says "King William gave the county of Northampton to Earl Waltheof", and links that to the marriage with Judith. It seems likely that Waltheof had been granted Northampton and Huntingdon before the Norman invasion (probably at the end of October 1065, when Tostig was banished and Morcar took over Northumbria, see: King Edward of Holy Memory), so Orderic's reference might tend to suggest that King William re-granted Waltheof his old earldom, following the latter's submission in January 1070.
Meanwhile, the happy political conditions on the other side of the Channel - giving William the domestic security which enabled him to successfully conquer England - had changed. William's father-in-law, Count Baldwin V of Flanders, died in 1067. (From 1060 to his death, Baldwin had acted as regent to his young nephew, King Philip I of France). The new count of Flanders was Baldwin V's son, Baldwin VI. He died three years later, and was succeeded, in name anyway, by his fifteen year old son, Arnulf III. The real driving force in Flanders was Arnulf's mother, Richildis of Hainault. Her oppressive government gave rise to a rebellion. The rebels invited Richildis' late husband's brother, Robert 'the Frisian', to invade Flanders. King Philip entered the contest on behalf of Arnulf. Orderic Vitalis says that King William had recently sent Earl William fitz Osbern to Normandy - to act, along with Queen Matilda, as regent. King Philip "summoned" Earl William to accompany him on the campaign. Orderic reports that the earl "took only ten men to the king's army, and rode off gaily to Flanders as though he were going to a tournament".
Normandy and Flanders were fiefdoms of France. Earl William, as regent, was fulfilling the feudal obligations of the duke of Normandy.  Note
"... but Robert came there and slew Arnulf his kinsman and Earl William, and put the king to flight, and slew many thousands of his men."
'Anglo-Saxon Chronicle' Manuscript D
This battle (the battle of Cassel), took place in February 1071. The upshot was that King Philip made peace with Robert, who became count of Flanders (Robert I).
"But mutual and lasting hostility arose between the Normans and Flemings ..."
Orderic Vitalis
The death of Geoffrey 'Martel' (Count Geoffrey II) of Anjou, in 1060, was followed by a protracted dispute between his nephews (Geoffrey had died childless): Geoffrey 'le Barbu' (Count Geoffrey III) and, his younger brother, Fulk 'le Rechin'. William 'the Bastard', duke of Normandy (and future king of England), took advantage of Anjou's preoccupation, and, c.1063, conquered Maine (which acted as a buffer-zone between Anjou and Normandy). In 1068, Fulk (Count Fulk IV) finally threw his brother into prison.
"... Fulk resented the lordship of the Normans in Maine and their arbitrary dominance of a country that was rightly his."
Orderic Vitalis
In 1069, there was a nationalist rebellion in Maine. Norman rule there collapsed. The resulting government, headed by one Geoffrey of Mayenne, however, was unstable. In 1072, the citizens of Le Mans invited Count Fulk's intervention on their behalf. Fulk, of course, obliged, and assisted them to drive out Geoffrey of Mayenne. So it was that, in 1073:
"... King William led an army, English and French, over sea, and won the district of Maine; which the English very much injured by destroying the vineyards, burning the towns, and spoiling the land. But they subdued it all into the hand of King William, and afterwards returned home to England."
'Anglo-Saxon Chronicle' Manuscripts D and E
The following year, King William, once more, crossed the Channel to Normandy. Edgar the Ætheling, too, had travelled overseas. It appears he had been to Flanders (where he, no doubt, would have been warmly received by Count Robert) since:
"... Eadgar Cild [Edgar the Ætheling ] came from Flanders into Scotland on St.Grimbald's mass-day [8th July 1074]; where King Malcolm and his sister [Edgar's sister, Malcolm's wife] Margaret received him with much pomp. At the same time sent Philip, the King of France, a letter to him [Edgar], bidding him to come to him, and he would give him the castle of Montreuil; that he might afterwards daily annoy his enemies [i.e. the Normans]. What then? King Malcolm and his sister Margaret gave him [Edgar] and his men great presents, and many treasures; in skins ornamented with purple, in pelisses made of marten-skins, of grey-skins, and of ermine-skins, in palls, and in vessels of gold and silver; and conducted him and his crew with great pomp from his [Malcolm's] territory. But in their voyage evil befel them [Edgar and his men]; for when they were out at sea, there came upon them such rough weather, and the stormy sea and the strong wind drove them so violently on the shore, that all their ships burst, and they also themselves came with difficulty to the land [the English coast]. Their treasure was nearly all lost, and some of his men also were taken by the French [Normans]; but he himself and his best men returned again to Scotland, some roughly travelling on foot, and some miserably mounted. Then King Malcolm advised him [Edgar] to send to King William over sea, to request his friendship, which he did; and the king gave it him, and sent after him. Again, therefore, King Malcolm and his sister gave him and all his men numberless treasures, and again conducted him very magnificently from their territory. The sheriff of York came to meet him at Durham, and went all the way with him; ordering meat and fodder to be found for him at every castle to which they came, until they came over sea to the king. Then King William received him with much pomp; and he was there afterwards in his court, enjoying such rights as he confirmed to him by law."
Anglo-Saxon Chronicle Manuscript D
In King William's absence, however, a conspiracy was developing in England. The 'Anglo-Saxon Chronicle' says that, in 1075:
". . . King William gave Earl Ralph the daughter of William fitz Osbern to wife."
Florence of Worcester, however, maintains that:
"Roger, earl of Hereford, son of William [fitz Osbern], earl of the same province, gave his sister in marriage to Ralph, earl of the East Angles, against the command of king William ..."
Both Roger and Ralph had succeeded to their father's earldoms. Earl Ralph is known as Ralph 'of Gael' (or Ralph 'Guader') after his holdings in Brittany. His father was Ralph 'the Staller'. This elder Ralph, made earl of East Anglia by King William, had, before the Conquest, served King Edward. He probably died in 1069. The 'Chronicle' says that the younger Ralph "was Breton on his mother's side; but his father, whose name was also Ralph [i.e Ralph the Staller], was English; and born in Norfolk". Ralph, however, is not an English name, and there is speculation that Ralph the Staller's father had come to England when Emma of Normandy crossed the Channel to marry Æthelred, in 1002. Wace notes that Ralph of Gael "was Breton and led a troop of Bretons" against the English at the battle of Hastings.
At any rate, at the wedding celebrations (Note):
"There was Earl Roger, and Earl Waltheof, and bishops, and abbots; who there resolved, that they would drive their royal lord out of his kingdom... It was Earl Roger and Earl Ralph who were the authors of that plot; and who enticed the Bretons to them, and sent eastward to Denmark after a fleet to assist them."
'Anglo-Saxon Chronicle'
"... they compelled earl Waltheof, who had been entrapped by their wiles, to join them in the plot."  Note
Florence of Worcester
Orderic Vitalis puts words into the mouths of the three earls. Ralph and Roger tell Waltheof: "Join our party and stand with us; we can promise you a third part of England. We wish to restore all the good customs that the realm of Albion enjoyed in the time of the virtuous King Edward. One of us shall be king and the other two dukes ..."  In his reply, Waltheof says: "King William has lawfully received the oath of fealty which I his vassal rightly swore, and has given his niece to me in marriage as a pledge of lasting loyalty. He has given me a rich earldom and counted me amongst his closest friends. How can I be unfaithful to such a lord, unless I utterly desecrate my faith? I am known all over the country, and it would cause great scandal if - which Heaven forbid - I were publicly proclaimed a sacrilegious traitor... The law of England punishes the traitor by beheading, and deprives his whole progeny of their just inheritance. Heaven forbid that I should stain my honour with the guilt of treachery, and that such shame should be voiced abroad about me."  Having declined the earls' invitation to join their plot, Waltheof is obliged to take "a terrible oath" not to reveal their plans.
Roger returned to Herefordshire, and Ralph, with his new wife (whose name, incidentally, was Emma), went to Norwich. Waltheof, however:
"As soon as he was able ... went to Lanfranc, archbishop of Canterbury, and accepting penance for his compulsory oath, by his advice applied to king William, who was then in Normandy, and having related the affair from beginning to end, voluntarily threw himself upon the royal clemency [Note]. But the chiefs of the conspiracy ... began by every exertion, with the aid of their supporters, to exite the rebellion."
Florence of Worcester
It is apparent that Lanfranc was acting in a governmental capacity during the king's absence. There exists a series of letters, written, during this period, by Lanfranc to Earl Roger. It is clear that Roger was definitely not a 'chip off the old block', and Lanfranc's disappointment is obvious.   Add.11
"William of Warenne and Richard of Bienfait, son of Count Gilbert [of Brionne], whom the king had appointed among his chief ministers for all business in England, summoned the rebels to the king's court. They however, scorned the summons, preferring to continue in their evil ways, and joined battle with the king's men."
Orderic Vitalis
"... Wulfstan, bishop of Worcester, with a great force, Æthelwig, abbot of Evesham, with his followers, and having procured the assistance of Urse, sheriff of Worcester, and Walter de Lacy, with their forces, and a large number of the people, prepared to prevent the earl of Hereford from crossing the Severn and joining earl Ralph and his army at the appointed place. Odo bishop of Bayeux, the king's brother, and Geoffrey, bishop of Coutances, with a great force, both of English and Normans, ready for action, met earl Ralph encamped near Cambridge."
Florence of Worcester
Orderic doesn't mention the two bishops, but says it was William of Warenne and Richard of Bienfait who:
"... mustered the English army and engaged in a hard-fought battle with the rebels in a plain called Fagaduna. Holding their ground they won the field by God's help, and left their mark on all prisoners of whatever rank by cutting off their right foot."
"But he [Earl Ralph], perceiving that his plan was frustrated ... escaped secretly to Norwich ..."
Florence of Worcester
"... they pursued Ralph the Breton to his castle, but could not capture him. Then concentrating their forces they besieged and attacked Norwich ... For three months they continued their relentless pressure, wearing out the enemy... When Ralph of Gael realized that he was shut in without hope of receiving any help from his accomplices, he entrusted the defence to a loyal garrison and himself took to the sea near by and boarded a ship to seek help in Denmark."
Orderic Vitalis
The 'Chronicle' and Florence say that Ralph left his wife in charge of the castle. The 'Chronicle' doesn't give Ralph's destination, but Florence says he sailed to Brittany. In view of what was to happen, however, it may be that Ralph did travel by way of Denmark. Orderic claims that William of Warenne and Richard of Bienfait sent messages to King William urging him to "return with all speed" to England. In fact, Archbishop Lanfranc wrote to the king informing him that everything was under control and there was no need for his return.
"... the leaders laid siege to his [Ralph's] castle, until the proclamation of peace by the permission of the king allowed his countess and her people to depart from England....
She joined Ralph in Brittany. Of course, Ralph forfeited his English estates, but, his Breton lands, as Orderic notes, "the English monarch had no power to confiscate". Lanfranc wrote to King William, informing him of the surrender of Norwich Castle (which was now in the hands Bishop Geoffrey, William of Warenne and Robert Mallet) and the end of the revolt. He says that Earl Ralph's Breton tenants had been given forty days to leave England, whilst his Breton mercenaries were allowed a month in which to depart. Apparently, Earl Roger had requested a meeting with Lanfranc, but Lanfranc wrote back to him saying, much as he would like to, he dared not for fear of the king. The archbishop told Roger to "lie low", and that he (Lanfranc) would inform King William of his (Roger's) penitence, and give him all the help he could. In another letter, to Bishop Walcher of Durham, Lanfranc writes: "...now that the Bretons are banished and all warfare is suppressed, we live in a tranquility greater than we can recall ever experiencing since the king crossed the sea. Be assured that our lord the king's affairs are prospering and that he himself is crossing to England without delay. The Danes are indeed coming, as the king told us. So fortify your castle with men, weapons and stores: be ready."
.... These things being done, the king returned in the autumn from Normandy, and put earl Roger in confinement, and delivered earl Waltheof to custody, though he had implored his mercy."
Florence of Worcester
"Soon after this came from Denmark two hundred ships; wherein were two captains, Cnut, son of King Swegn, and Earl Hakon; and they durst not maintain a fight with King William, but ..."
'Anglo-Saxon Chronicle'
At this point Manuscript E simply says the Danes went "over sea to Flanders" (Florence does not record this incident at all), but Manuscript D reports that they:
"... went to York, and broke into St.Peter's minster, and took therein much treasure, and so went away. But they all perished who were privy to that design; that was, the son of Earl Hakon, and many others with him."
Edith, widow of King Edward and sister of King Harold, died at Winchester, "seven nights" before Christmas 1075. King William had her body taken to Westminster and buried, "with honour", alongside her husband.
"The king was then at Westminster, at midwinter; where all the Bretons were condemned who were at the bride-ale at Norwich. Some were punished with blindness; and some were banished from the land; and some were put to shame. So were the traitors to the king subdued."
'Anglo-Saxon Chronicle'
"Earl Roger ... was judged by the laws of the Normans, and condemned to perpetual imprisonment after forfeiting all his earthly goods."
Orderic Vitalis
According to Orderic, Roger added insult to injury by burning some fine garments which King William had sent to him, one Easter, in prison. On the one hand, Orderic is adamant that Roger was never released: "The king's sentence was so lasting that even after the king's death nothing but death released him from his fetters."  But on the other, he (and also Florence of Worcester) names Earl Roger amongst the prisoners whose release King William ordered, from his deathbed, in 1087.
"Earl Waltheof was summoned before the king and accused, on the deposition of his wife Judith, of being a party to the conspiracy and proving unfaithful to his lord. He, however, fearlessly and openly admitted that he had learned from the traitors of their infamous intention, but had refused to give them any support in such a shameful affair. Judgement was demanded on the grounds of this confession: but as the judges could not agree among themselves a decision was postponed several times ... During this time the brave earl was kept in the king's prison at Winchester ..."
Orderic Vitalis
"And this year [1076] was Earl Waltheof beheaded at Winchester, on the mass-day of St.Petronella [31st May]; and his body was carried to Crowland, where he lies buried."
'Anglo-Saxon Chronicle' Manuscript D
Florence says that Waltheof was beheaded, with an axe, "outside the city of Winchester". His body was initially buried at the execution site, but later "carried with great honour to Crowland, and honourably buried in the church". Orderic Vitalis notes that "Earl Waltheof was a good friend and brother of the abbey of Crowland".
It is evident that Waltheof had a skald,Thorkell Skallason, in his entourage. Two stanzas by Thorkell, concerning Waltheof, appear in 'Heimskringla'. The first tells how he caused a hundred Normans to burn to death (Note). The second (here rendered in prose) laments his death:
"It is certain that William, the reddener of weapons, he who clove the foamy sea from the south, has kept bad faith with valiant Waltheof. Truly it will be long before slaying of men ceases in England - but my lord was gallant! No more famous chief than he will die in England."
'Valþjófsflokkr'
"This man [Waltheof], while yet in the enjoyment of life, being placed in close confinement, lamented without ceasing and with extreme bitterness the unrighteous actions of his past life. He earnestly sought to appease his God by vigils, prayers, fastings, and almsgiving; men desired to blot the remembrance of him on earth; but we firmly believe that he is now rejoicing with the saints in heaven, on the testimony of archbishop Lanfranc of pious memory, from whom he received the sacrament of penance after his confession, who declared that not only was he guiltless of the crime laid to his charge, the conspiracy mentioned above, but that, like a true Christian, he had lamented with tears of penitence the other sins which he had committed; and he added that he himself should esteem himself happy could he enjoy, after his own departure, the blessed repose of the earl."
Florence of Worcester
"... some assert that he joined the league of treachery more through necessity than inclination. This is the excuse the English make for him, and those, of the greater credit, for the Normans affirm the contrary, to whose decision the Divinity itself appears to assent, showing many and very great miracles at his tomb; for they declare that during his captivity, he wiped away his transgressions by daily sorrow."
"They [the monks of Crowland] cherished his body much, and it was often seen afterwards in this place, that God, through it, worked many miracles."
Orderic Vitalis spent five weeks at Crowland - where the cult of Waltheof was fostered. As a result, his story becomes more hagiography than history. However, Orderic says that Waltheof ("a handsome man of splendid physique") had been taken to his place of execution - St.Giles' Hill, outside Winchester - very early in the morning, whilst people were still asleep. Once there, Waltheof gave away his rich garments to the few clergy and poor who were present, and prostrated himself in prayer. After some considerable time, his executioners, anxious to get the job over before the citizens awoke and intervened to prevent the sentence being carried out, told him to get up. He asked to be allowed to say the Lord's prayer:
"As they agreed he rose, and kneeling with his eyes raised to heaven and his hands stretched out he began to say aloud, 'Our Father, which art in Heaven'. But when he reached the last sentence and said, 'And lead us not into temptation,' such tears and lamentations broke from him that he could not finish his prayer. The executioner refused to wait any longer, but straightway drawing his sword struck off the earl's head with a mighty blow. Then the severed head was heard by all present to say in a clear voice, 'But deliver us from evil. Amen.'"  Note
Waltheof's body was flung into a ditch and covered with turf (Note). A fortnight later, "at the request of Judith and with the king's permission", the abbot of Crowland dug up the body ("which still remained incorrupt with blood as fresh as if he had just died"), transported it to Crowland and buried it in the chapter-house. When the body had been interred "for nearly sixteen years", it was decided to move it into the church. When the coffin lid was opened the corpse was "found as incorrupt as on the day of its burial, and moreover the head was joined to the body". It was in "the third year" of Geoffrey, abbot of Crowland 1109-24, that miracles first began to occur at Waltheof's tomb, and "grew daily more frequent". During his stay at Crowland, Orderic himself was asked to compose an epitaph for Waltheof:
Beneath this stone a man of highest virtue -
The valiant son of Siward, earl and Dane -
Waltheof, most glorious earl, lies nobly buried.
Honoured in war, revered by all, he flourished;
Yet knowing worldly wealth and fame are shadows
He gave his love to Christ, and sought to please him,
Cherished his Church, and humbly loved his clergy,
Cherishing most the faithful monks of Crowland.
Sentenced to die by cruel Norman judgement,
At the last dawn of May he fell, beheaded.
The marshy soil of Crowland which, while living,
He had so deeply loved received his body.
God grant his soul eternal rest in Heaven.
Waltheof's widow, Judith, inherited most of the lands associated with his Midlands earldom - in the 'Domesday Book' she appears as Countess Judith. Waltheof's Northern earldom, however, was handed to Bishop Walcher of Durham. Meanwhile, still in 1076:
"King William now went over sea, and led his army to Brittany, and beset the castle of Dol ....
Where, it appears, Ralph of Gael was holed-up.
.... but the Bretons defended it, until the king [Philip] came from France; whereupon King William departed thence, having lost there both men and horses, and countless treasures."
'Anglo-Saxon Chronicle' Manuscript D
"This year [1077] were reconciled the king of the French and William, king of England. But it continued only a little while."
'Anglo-Saxon Chronicle' Manuscript E
Local Difficulties    
Translations:
'Valþjófsflokkr' by Forrest S. Scott
Roger of Hoveden 'Chronica' by Henry T. Riley
Robert Wace 'Roman de Rou' by Edgar Taylor
Orderic Vitalis 'Historia Ecclesiastica' by Marjorie Chibnall
'Anglo-Saxon Chronicle' by Rev. James Ingram/Dr. J.A. Giles
Geffrei Gaimar 'L'Estoire des Engleis' by Rev. Joseph Stevenson
'The Letters of Lanfranc Archbishop of Canterbury' by Helen Clover and Margaret Gibson
Symeon of Durham 'Historia Regum' & 'Historia Ecclesiae Dunelmensis' by J. Stevenson
William of Malmesbury 'Gesta Regum Anglorum' by Rev. J. Sharpe, revised by Rev. J. Stevenson
Florence of Worcester 'Chronicon ex Chronicis' edited and in part translated by Joseph Stevenson