Kveldulf was the son of Bjalfi and Hallbera Ulfsdóttir, daughter of Ulf the Brave and sister of Hallbjorn Halftroll. He was thus first cousin to Ketil Trout of Halogaland and a kinsman of the latter's descendant, Ketil Trout of Namdalen.Landnamabok 5:3. Kveldulf married Salbjorg Karadottir, the daughter of the Viking chieftain Berle-Kari; he was thus the brother-in-law of the Viking Eyvind Lambi and the skald Olvir Hnufa.
