How could the cruel House Bolton be a banner man or ally of the honorable House Stark?

Question

House Bolton is known for flaying their enemies. Their sigil is even a flayed man. Robb Stark executed Lord Karstark for injustice knowing he would lose his alliance with House Karstark. So how could Robb Stark have been an ally of Roose Bolton? And more generally how could the houses have a history together given Ned's honor and Bolton's cruelty?

Was it just one of those unholy alliances that always goes bad? Or was there some explanation about why Robb would tolerate such a House in his midst?

Answer 1

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 flayed.

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.

Answer 2

Historically, they lived in the same kingdom (The North), and therefore were under the rule of the Stark Kings of old.

House Bolton is more like Slytherin, in that they're not inherently evil but more cunning and ambitious and will do whatever it takes. This is the problem as sometimes "whatever it takes" ends up involving deceit and other horrible means of getting ahead; such as betraying your Liege Lord by stabbing them through their heart - both literally and figuratively.

Remember, Bolton didn't show his "true colours" until very late in the game; and until then had been a steadfast battle commander. So it would have been quite difficult to pick out his upcoming defection.

Allies is too strong a term to attribute to their relationship. House Stark was the liege lord of House Bolton, and as such, the Boltons had no choice but to go to war with them when called. The problem with 'deception' is that it is deceiving - you don't see it coming.

There is evidence in the books as well that even Robb himself didn't feel happy about Roose Bolton or his involvement in the enterprise:

[Catelyn] “No. You want cold cunning, I should think, not courage.”
[Robb] “Roose Bolton,” Robb said at once. “That man scares me.”
[Catelyn] “Then let us pray he will scare Tywin Lannister as well.”
^{-A Song of Ice and Fire: Book One - A Game of Thrones, Chapter 55 (Catelyn VIII).}

---

Further Reading

• What was the relation between Eddard Stark and Roose Bolton?
• Did Jaime realise what Bolton's motivation was?
• Why is the Bolton banner a flayed man?

Answer 3

Ok, the Boltons are kinda weird. But you see the reason why nobody really seems to despise them is because noone is really different. The Lannisters with their shiny gold are not more or less cruel, then the Boltons, they just hide it behind shiny golden plates, just as the Baratheons and many other houses, also the starks were not always so honourable, only the latest generations. Furthermore even for North Standarts the Starks were unnaturally honourable, the Northeners are actually more harsh and hard people who have their sacreds like even the Boltons would never slay their kin or break the guest right, however loyality to the Stark is not something the Boltons would brag with as they are ancient rivals. I see the Banner and the words (a flayed man holds no secrets) of the Boltons more metaphorical, like the Boltons ARE the flayed men, and they are openly doing what everyone else does because they don't care, they make no secrets of their cruelty.