Née en l'an 264, lady Catelyn Stark, est la fille aînée de lord Hoster Tully et de lady Minisa Whent. Elle est l'épouse de lord Eddard Stark, le sire de Winterfell, et la mère de ses cinq enfants légitimes : Robb, Sansa, Arya, Brandon et Rickon. Catelyn est une belle femme dotée des caractéristiques physiques des membres de la maison Tully de Vivesaigues : ses cheveux épais sont auburn, ses yeux, bleus, son teint, clair et ses pommettes hautes.

Elle est une épouse aimante et une mère attentionnée. Très protectrice, elle connaît la plus grande difficulté à se séparer de ses enfants. Elle se montre, de même, très fière de leurs prouesses et talents. Elle éprouve en revanche un ressentiment tenace (mêlé cependant de culpabilité) envers Jon Snow, fils bâtard de son époux, élevé à Winterfell comme l'un de ses fils légitimes. Elle n'a jamais pu découvrir ou faire avouer à Ned qui était la mère de son bâtard. Quand elle s'est ouverte à lui des bruits qui nommaient lady Ashara Dayne, Eddard lui a répondu froidement qu'elle n'avait pas à connaître qui était la mère de Jon et qu'il était « de son sang ». Ned prend alors des mesures pour que le nom de lady Ashara ne soit plus prononcé devant sa femme. De fait, Jon représente la seule partie du cœur de Ned qu'elle ne peut atteindre. Bien qu'il lui ait toujours montré le plus grand respect, lady Catelyn n'éprouve guère d'affection pour le pupille de son mari, Theon Greyjoy, l'héritier de lord Balon, accueilli comme otage à Winterfell après la fin de la rébellion des Greyjoy. Elle se méfie de sa famille, et le petit sourire sarcastique qu'il arbore en permanence l'exaspère.

Son rôle de fille aînée destinée à un mariage politique, les absences de son père durant son enfance, le départ de Brandon pour Port-Réal après l'enlèvement de Lyanna et enfin le départ d'Eddard pour la guerre, donnent à Catelyn l'impression qu'elle passe sa vie cantonnée dans un rôle passif et attentiste. Elle est pourtant une femme volontaire, forte, et capable de prendre des décisions dans l'urgence. De même, elle n'a pas un rôle effacé vis-à-vis de lord Eddard qui écoute volontiers ses conseils. Catelyn n'a d'ailleurs rien à envier à son époux sur tout ce qui touche à la fierté, à l'honneur et au sens du devoir. Elle est toutefois plus souple, pragmatique et diplomate que ce dernier. Elle porte généralement un regard lucide sur la valeur des gens qu'elle connaît, notamment les vassaux de son époux et de son père. Peu encline au laisser-aller, lady Stark ne montre que rarement ses émotions et n'est guère indulgente vis-à-vis d'elle-même, se reprochant avec amertume ses erreurs ou ce qu'elle estime telles. Tenaillée fréquemment par le doute, elle se remet souvent en question. Très consciente de son rang, elle peut parfois s'avérer des plus hautaines et dédaigneuses à l'égard du peuple. Son aversion pour les bâtards ne concerne d'ailleurs pas que Jon. Catelyn est également une femme pieuse, adepte de la Religion des Sept.