Waltheof was the second son of Siward, Earl of Northumbria. His mother was Aelfflaed, daughter of Ealdred, Earl of Bernicia, son of Uhtred, Earl of Northumbria. In 1054, Waltheof’s brother, Osbearn, who was much older than he, was killed in battle, making Waltheof his father’s heir. Siward himself died in 1055, and Waltheof being far too young to succeed as Earl of Northumbria, King Edward appointed Tostig Godwinson to the earldom.
Waltheof was said to be devout and charitable and was probably educated for a monastic life. Around 1065, however, he became an earl, governing Northamptonshire and Huntingdonshire. Following the Battle of Hastings he submitted to William and was allowed to keep his pre-Conquest title and possessions. He remained at William’s court until 1068.
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 1072, he was appointed Earl of Northampton.
The Domesday Book mentions Waltheof ("Walleff"): "'In Hallam ("Halun"), one manor with its sixteen hamlets, there are twenty-nine carucates to be taxed. There Earl Waltheof had an "Aula" . 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.