Eldest child of Lord Hoster Tully of Riverrun and his lady wife Minisa Whent, born in 264 AC and raised at her father's seat alongside her sister Lysa and the young ward Petyr Baelish. At twelve she was betrothed to Brandon Stark, heir to Winterfell, and when Brandon was murdered in King's Landing on the order of Aerys II the betrothal passed to his younger brother Eddard. She wed Lord Eddard at Riverrun in 283 AC on the same day her sister was given to Lord Jon Arryn, and bore him five children — Robb, Sansa, Arya, Bran, and Rickon — and kept his northern hall through the long years of his stewardship, though she never reconciled herself to his bastard Jon Snow being raised beside her own.
When her sister wrote that the Lannisters had murdered Lord Jon Arryn she pressed Eddard to accept King Robert's offer of the Handship, and rode south herself to warn him of the catspaw who had come for Bran. On the way home she took Tyrion Lannister captive at the inn at the crossroads and bore him into the Vale, a stroke that loosed Lord Tywin's host upon the riverlands and her son Robb upon the war road. Through the first year of the war she rode at Robb's side — brokering the crossing at the Twins with Lord Walder Frey, treating with Renly and Stannis Baratheon at Storm's End and Bitterbridge, fleeing north with Brienne of Tarth in her service after a creature of shadow took Renly at the parley. In a last attempt to recover her daughters from King's Landing she freed the captive Ser Jaime Lannister under Brienne's keeping, for which act Robb's bannermen turned cool and called her false.
Catelyn rode with her son to the Twins for Edmure's wedding to Roslin Frey, and there sat between Ser Ryman Frey and Lord Roose Bolton at the high table as Lord Walder's hall came down upon the Stark host in the slaughter that would after be called the Red Wedding. She seized Walder's lackwit grandson Aegon and offered his life for Robb's; when Bolton put the knife through her son she opened the boy's throat with her own hand and clawed her face to ribbons before Ser Raymund Frey cut her down. The Freys dumped her naked body into the Green Fork, where three days later the brotherhood without banners drew her from the water, and Lord Beric Dondarrion gave his own life for hers through the last kiss — raising her up as Lady Stoneheart, half-rotted and unable to speak save by pinching closed her slit throat, to hang Freys and Boltons and Lannisters along every road of the riverlands until the war is paid.