Com a chegada da caravana real à Winterfell, Catelyn recebeu uma carta secreta de sua irmã Lysa que dizia que os [[Lannister]] haviam matado seu marido, [[Jon Arryn]], a [[Mão do Rei]] anterior. Isso alertou os [[Casa Stark|Stark]], já que o cargo acabara de ser oferecido pelo [[Robert Baratheon|Rei Robert]] à Eddard. Catelyn incentivou Ned a aceitar a oferta, além de também concordar em prometer a filha Sansa ao [[Joffrey Baratheon|Príncipe Joffrey]] na esperança de que a filha se tornasse rainha um dia. Apesar de suas dúvidas, Ned acabou aceitando.
Quando Bran sofreu uma queda de uma torre e acabou entrando em estado de coma, Catelyn se manteve ao seu lado por oito dias, ignorando suas demais obrigações em Winterfell. Na oitava noite, ela foi atacada por um [[Assassino de aluguel|assassino ]] que viera matar Bran e teve suas mãos feridas por uma lâmina. Ela e o filho foram salvos por [[Verão]], o [[lobo gigante]] de Bran. Após se recuperar, Catelyn viajou para Porto Real com Sor [[Rodrik Cassel]] para relatar ao marido o que havia acontecido. Em [[Porto Real]], seu amigo de infância, Petyr, a encontrou em um de seus bordéis e contou que a adaga que o [[Assassino de aluguel|assassino ]] portava pertencia a [[Tyrion Lannister]].
Na volta para Winterfell, ela encontrou e tomou Tyrion como cativo na [[Estalagem do Entroncamento]] ao invocar a cavaleiros de vassalos do pai que a ajudassem a levar o anão à justiça. Apesar de anunciar para todos que levaria Tyrion para Winterfell, ela partiu para o [[Ninho da Águia]] para que Lysa o julgasse. A viagem do grupo foi dura, e eles foram atacados diversas vezes por clãs das [[Montanhas da Lua]]. No Ninho, Tyrion foi jogado nas celas do céu, mas escapou da execução ao convencer [[Bronn|um mercenário]] a lutar por ele num julgamento por combate. Enquanto isso, a prisão do anão despertou a fúria de Lorde [[Tywin Lannister]], que enviou Sor [[Gregor Clegane]] sob disfarce para que pilhasse as Terras Fluviais. As tensões entre a Casa Tully e a Casa Lannister foram um dos estopim para a [[Guerra dos Cinco Reis]].