In 1070 Waltheof married Judith de Lens, daughter of Lambert II, Count of Lens and Adelaide of Normandy, Countess of Aumale. They had three children, the eldest of whom, Maud, brought the earldom of Huntingdon to her second husband, David I of Scotland, and another, Adelise (Alice of Nothumbria) married the Anglo-Norman noble Raoul III of Tosny.