Here's some background about the relations between the Starks and the Boltons from The World of Ice & Fire: the Untold History of Westeros and the Game of Thrones by George R.R. Martin, Elio Garcia, and Linda Antonsson.
Yet the bitterest foes of Winterfell were undoubtedly the Red Kings of
the Dreadfort, those grim lords of House Bolton whose domains of old
stretched from the Last River to the White Knife, and as far south as
the Sheepshead Hills.
The enmity between the Starks and Boltons went back to the Long Night
itself, it is claimed. The wars between these two ancient families
were legion, and not all ended in victory for House Stark. King Royce
Bolton, Second of His Name, is said to have taken and burned
Winterfell itself; his namesake and descendant Royce IV (remembered by
history as Royce Redarm, for his habit of plunging his arm into the
bellies of captive foes to pull out their entrails with his bare hand)
did the same three centuries later. Other Red Kings were reputed to
wear cloaks made from the skins of Stark princes they had captured and
Yet in the end, even the Dreadfort fell before the might of
Winterfell, and the last Red King, known to history as Rogar the
Huntsman, swore fealty to the King of Winter and sent his sons to
Winterfell as hostages, even as the first Andals were crossing the
narrow sea in their longships.
After the defeat of the Boltons, the last of their Northern rivals,
the greatest threats to the dominion of House Stark came by sea.
Crossing the narrow sea in their hundreds and thousands, the longships
of the Andals made landings in the North just as they did to the
south, but wherever they came ashore, the Starks and their bannermen
fell upon them and drove them back into the sea. King Theon Stark,
known to history as the Hungry Wolf, turned back the greatest of these
threats, making common cause with the Boltons to smash the Andal
warlord Argos Sevenstar at the Battle of the Weeping Water.