Desde a [[Longa Noite]], os Reis Vermelhos foram grandes rivais dos [[Casa Stark|Starks]] de [[Winterfell]], que governavam como [[Rei da Noite|Reis do Inverno]]. Os Boltons conseguiram travar algumas guerras bem sucedidas contra os Starks, com os reis [[Royce II Bolton|Royce II]] e [[Royce IV Bolton|Royce IV]] saqueando Winterfell.{{ref|TWOIAF| The North: The Kings of Winter}} É dito que os Boltons esfolaram vários Starks e deixavam suas peles a mostra adornando o Forte do Pavor. Segundo um rumor, alguns lordes Boltons utilizavam peles de Starks e outros inimigos capturados como casaco.{{ref|ACOK|51}} A prática do esfolamento deu aos Boltons uma reputação sinistra pelo Norte. O último Rei Vermelho foi [[Rogar Bolton|Rogar, o Caçador]], que se submeteu a Winterfell no início da [[Invasão Ândala]] de [[Westeros]]. O rei [[Theon Stark]], o Lobo Faminto, uniu forças com os Boltons e derrotou [[Argos Setestrelas]] e seu exército [[Ândalos (Povo)|ândalo]] na [[Batalha das Águas Chorosas]].{{ref|TWOIAF| The North: The Kings of Winter}}
Com o passar dos anos, os Boltons eventualmente se ergueram em revolta contra os Starks, se aliando certa vez com os [[Cassa Casa Greystark|Greystarks]], por exemplo. Enquanto os Greystarks acabaram extintos, os Boltons sobreviveram.{{Ref|ADWD|29}}
Os Boltons chegaram a ameaçar Winterfell durante o reinado de [[Edrick Stark]].{{ref|TWOIAF| The North: Winterfell}} Séculos mais tarde, os Boltons mais uma vez se rebelaram. Os Stark cercaram o Forte do Pavor e eventualmente os Boltons novamente dobraram o joelho para o rei [[Harlon Stark]].{{ref|ADWD|17}}