She is the daughter of Hostor Tully and Minisa, formerly of house Whent. She has five children: Robb, Sansa, Arya, Bran and Rickon.
She spent her childhood in Riverrun, where she befriended her father's ward, Petyr Baelish. Although he fell in love with her and would have liked to marry her, Catelyn never shared his feelings because she could not see him as more than a younger brother. When she was twelve, it was announced that she was betrothed to Brandon Stark, heir of Winterfell, in what would strengthen the ties of friendship between the great houses. When Brandon came to Riverrun to meet with Catelyn, young Petyr challenged him to a duel for her hand, but Brandon beat him easily. Catelyn begged that Baelish's life be spared and Baelish was banished from Riverrun back to his own home as soon as he was sufficiently recovered. He later sent a single letter after Brandon's death, but Catelyn burned it without reading it. Catelyn's betrothal with Brandon ended abruptly when he, along with his father, were killed by the Mad King, setting off Robert's Rebellion, which was led by his younger brother Eddard Stark, and his childhood friend Robert Baratheon. During the Rebellion, Catelyn father sought to continue the alliance and she ended up marrying Eddard. She moved to Winterfell, where she and Eddard formed a strong and loving marriage, and where they are well respected and loved by both nobles and smallfolk. Catelyn and Eddard have five children: Robb, Sansa, Arya, Bran and Rickon and they raised Eddard's bastard son Jon Snow, the single act that created friction between her and her husband.
- In A Game of Thrones, after the royal party arrives at Winterfell, Catelyn received a letter from her sister Lysa that stated the Lannisters had killed her husband Jon Arryn, the late Hand of the King. Robert I had offered Ned the position, and Catelyn pushes her husband to accept the offer along with a betrothal that would make Sansa queen one day, and, despite misgivings about going to the capitol, Ned eventually accepted. When Bran fell comatose after apparently falling while climbing one of Winterfell's keeps, Catelyn stayed by his side for eight days, but, on the eighth night, she gets attacked by an assassin who had come for Bran and her hands get injured before the man is killed by Bran's direwolf. After recovering from the attack, Catelyn traveled to King's Landing along with Ser Rodrik Cassel to let Eddard know what had happened. There, her childhood companion Petyr Baelish met her in one of his brothels and told her that the dagger used in the attack belonged to Tyrion Lannister. On her way back to Winterfell, she happens upon Tyrion at the Inn at the Crossroads and she asks her father's bannermen to help her bring him to justice. Instead of taking him to Winterfell, she goes to her sister at the Eyrie for trial where Tyrion gets thrown into the Sky Cells and escapes execution by convincing a sellsword to fight in a trial by combat. Meanwhile, Tyrion's arrest has sparked the War of the Five Kings because Tywin Lannister ordered Ser Gregor Clegane and other raiders to attack the Riverlands in retribution. Robb marched south with his father's bannermen in response to Lord Eddard's arrest in King's Landing, and Catelyn goes to meet with House Manderly's levies with her uncle Ser Brynden Tully. When Robb is about to place Greatjon Umber in command of the infantry force sent to engage Tywin Lannister, Catelyn is able to convince him to appoint Roose Bolton, and she stays with the army to see her dying father instead of heading back to Winterfell. When the army found it necessary to cross the Trident, Cat went to negotiate with Lord Walder Frey and gained passage by promising (among other things) Robb's hand in marriage to one of Frey's daughters. After the news of Eddard's execution by order of King Joffrey reaches Catelyn, she is filled with grief but puts on a strong front for the sake of her son, and during the war council at Riverrun, Catelyn argues for peace with the south so that Sansa and Arya might be more easily brought to safety. Robb and the assembled lords make it clear that they intend to continue the war and Greatjon declares Robb the first King in the North in three centuries.
- In A Clash of Kings, Catelyn advised against Robb's plan to send Eddard's ward, Theon Greyjoy, on a diplomatic mission to forge an alliance with Balon Greyjoy because she did not trust either man. Catelyn has the idea to attempt to ally with Renly Baratheon and his massive Reach-Stormlands host, but, when Robb wants her to go as the envoy, she wishes to remain with her son. Catelyn eventually relented and went after accepting the fact that her son was becoming a man, and she traveled south to Bitterbridge where she found King Renly hosting a tourney. With Catelyn in tow, Renly then rode to Storm's End when he heard his brother Stannis was. She was present for the inconclusive parley between the two rival brothers, and she witnessed Renly's murder later that night by a shadow creature. Afterwards, Catelyn left with Brienne of Tarth, one of Renly's guard, and they made their way to Riverrun. Upon hearing of her younger sons' supposed murder at the hand Theon Greyjoy, she freed Robb's hostage Jaime Lannister in an attempt to exchange him for her daughters who are still captives at King's Landing. This, however, causes problems for Robb and costs him an ally who had held grudges against the Lannisters.
- In A Storm of Swords, Catelyn's brother Edmure Tully places Catelyn under house arrest at Riverrun, but Robb pardons her after he announces his wedding to Jeyne Westerling. She attends Edmure's wedding at the Twins with Robb and other northern lords, but the group is murdered by members of House Frey, an act of treachery that became known as the "Red Wedding". In an attempt to save her son's life, Catelyn took Aegon Frey hostage and killed him, but she still had her throat slashed by Raymund Frey. Three days later, Catelyn was resurrected by Lord Beric Dondarrion, who gave his life for hers, and she became known as "Lady Stoneheart". Catelyn's wounds only partially healed and she was left mutilated and unable to speak, and she became consumed with the desire for revenge for her family. Catelyn then assumed command of Dondarrion's outlaw band, the Brotherhood Without Banners, and she led the group in pursuing and executing everyone she considered a traitor, including Petyr and Merrett Frey.
- In A Feast for Crows, Catelyn, or Lady Stoneheart, and the Brotherhood come upon a small party led by Brienne. The female knight informs her that she is searching for Sansa at Jaime Lannister's request. Stoneheart says that Brienne is a traitor, because she carries Oathkeeper, a Lannister sword that was forged from the Stark Valyrian steel blade, Ice. Brienne swears that she is still faithful, but Stoneheart insists she must prove it by killing Jaime, which Brienne refuses to do even when threatened with a hanging. Just before Brienne is executed, she shouts out a word.