Catelyn é a esposa de Eddard Stark e Lady de Winterfell. Ela tem 5 filhos: Robb Stark, Sansa Stark, Arya Stark, Bran Stark e Rickon Stark.
Catelyn nasceu na Casa Tully, é a filha de Lord Hoster Tully e Minisa Tully, seus irmãos são Edmure Tully e Lysa Arryn. Catelyn é conhecida por seu senso de justiça e honra, tendo seu comportamento regido por príncipios.
Tem um amor profundo pela família e forte fé nos Sete. Ela nunca considerou o bastardo Jon Snow como parte da família e nunca perdoou Eddard por trazê-lo para casa.
História
Catelyn cresceu em Riverrun onde se tornou amiga de Petyr Baelish, um protegido de seu pai. Petyr se apaixonou por ela, mas ela sempre o considerou um irmão. Quando ela tinha 12 anos, foi prometida a Brandon Stark, herdeiro de Winterfell. Petyr desafiou Brandon em um duelo pela mão de Catelyn, porém ele foi derrotado e sobreviveu graças aos pedidos de Catelyn pela sua vida. Catelyn nunca mais falou com ele e queimou a única carta que ele lhe enviou após a morte de Brandon.
Apesar de amar e de estar noiva de Brandon, ela acabou se casando com seu irmão mais novo, Eddard, depois que Brandon foi morto pelo Rei Louco.
A Guerra dos Tronos
Depois da chegada da família real em **Wintefell** Catelyn recebeu uma carta de sua irmã, avisando que a os Lannisters mataram seu marido, a mão do rei, Jon Arryn. Isso deixa os Starks alarmados, já que Ned havia sido convocado para o mesmo cargo por Robert I.
Depois que Bran é atacado por um assassino, Catelyn viaja para Porto Real para informar Eddard sobre o ocorrido. Ao chegar, Catelyn é informada por Petyr Baelish que a adaga pertence a Tyrion Lannister.
Em seu caminho de volta para Winterfell, Catelyn encontra Tyrion e o leva preso para o vale de Arryn, lá Tyrion escapa de sua execução, mas sua prisão é o estopim para o início da guerra.