- "Love didn't just happen to us. We built it slowly, stone by stone, over the years."
- ―Catelyn Stark to Robb Stark
An Arranged Marriage
Catelyn Tully is the eldest daughter of Hoster Tully, Lord of Riverrun and Lord Paramount of the Riverlands. Her father had arranged for her to marry Brandon Stark, the eldest son and heir of Lord Rickard Stark, Lord of Winterfell and Lord Paramount of the North.
She has a younger sister named Lysa. Petyr Baelish is a ward of Hoster Tully. He was fostered at Riverrun; Catelyn, Lysa, and Petyr grew up together. When Catelyn becomes engaged, Petyr professes his love for her, and Brandon must fight a duel against him. Catelyn asks Brandon to spare Petyr's life. Petyr Baelish has remained obsessed with her.
Brandon's sister is Lyanna Stark, and she is betrothed to Lord Robert Baratheon of Storm's End. When word comes of her kidnapping by Prince Rhaegar Targaryen, Brandon rides to the capital to demand Lyanna's return and Rhaegar's death for his crimes. Aerys arrests Brandon for treason and demands that his father come to King's Landing to ransom him. When Brandon Stark and his father Lord Rickard Stark are executed by King Aerys, Catelyn's father then arranges for her to marry the new Lord of Winterfell, Eddard Stark, a virtual stranger to her. He is quiet and reserved, very unlike Brandon. Referred to as "Ned" by those who are close to him, he is stoic and honorable, embodying the values of the North. Lord Jon Arryn of the Eyrie and Lord Paramount of the Vale has been told to turn Eddard Stark and Robert Baratheon over for execution, but instead he joins forces with them in rebellion.
Catelyn and her sister Lysa are married, in a double ceremony, to Eddard Stark and Jon Arryn. Their new husbands are riding off with the Tully bannermen to war against Aerys. It will come to be known as Robert's Rebellion, and Robert Baratheon rules as king for the next 17 years. Catelyn conceives on her wedding night, and Eddard leaves her with child. Robb is born before his return. When next Catelyn sees Eddard, he has brought with him the bastard Jon Snow, his child with an unnamed woman. Eddard raises his bastard at Winterfell with his trueborn children. Catelyn comes to love her husband very much, but this constant reminder of her husband's infidelity and the threat to her own children's inheritance is the only black mark on her otherwise perfect marriage.
An Almost Perfect Marriage
Eddard and Catelyn Stark are looking down into the courtyard of Winterfell, as they watch Bran at archery practice. Though he misses several times, Arya hits a bull's-eye from a further distance. They smile as they watch Bran chase her from the courtyard. Ser Rodrik comes to tell Lord Eddard that a deserter from the Night's Watch has been captured. Catelyn questions not only the need for Eddard to go and execute the man, but more importantly his decision to take Bran, who is only 10 years old, to witness the execution. Eddard tells her that the man swore an oath, and Bran will not be a boy forever. He reminds her of the Stark words, "Winter is Coming". After Eddard departs, Catelyn watches Jon Snow gathering arrows in the courtyard. He looks up to see her expression of disdain.
After the execution, Eddard is in the godswood of Winterfell, sitting by the heart tree, cleaning his sword in quiet ritual. Catelyn hesitantly walks over to him. She remarks that, even after all the years of their marriage, she still feels like an outsider when she comes here, to this place of his northern Gods. He smiles at that saying that she isn't an outsider, as she has born five northern children. She questions whether the Old Gods agree with him, but he insists that it is her Gods that have all of the rules.
She then apologizes for the sad news she must relate. A raven has come to Winterfell from King's Landing, with word of the death of Jon Arryn, a man whom Eddard had thought of as a father. He died suddenly of a fever, but Lysa and their son are well. Catelyn sits beside Eddard to tell him the further news that King Robert Baratheon, Queen Cersei and others of the court are travelling north to Winterfell. Eddard immediately knows that the reason for this must be that Robert is planning to offer him the position that Jon Arryn had held as Hand of the King. Catelyn says that he can always refuse.
As they lay in bed in each other's arms, Eddard tells her that his place is in the north and not at court. Catelyn says that she will not allow Eddard to be taken from home, but Eddard knows that a king takes what he wants; this is how Robert Baratheon became king in the first place. Catelyn makes Eddard laugh by telling him how she will confront Robert, calling him "Fat Man" and denying him her husband's service. She says that Eddard belongs to her.
Maester Luwin knocks on the door. He apologizes, but a messenger has arrived from Lysa Arryn. Catelyn is surprised that Lysa is at the Eyrie. She reads the message and then quickly throws it on the fire. Lysa has written that she has fled the capital, believing her husband to have been murdered by the Lannisters. She also suspects that the king is in danger. Eddard wonders if her judgement might be clouded by grief, but Catelyn reasons that the very act of putting her suspicions in writing was such a risk to the safety, both of herself and her child, that she must be absolutely certain of her husband's murder. Maester Luwin surmises that if the Lannisters do plot against the king, Eddard would be Robert's best hope for protection. Catelyn disagrees with Luwin's advice, as the Lannisters murdered the last Hand of the King, how could Maester Luwin be advising Eddard to accept the post. However, he points out that Lord Stark has sworn an oath to Robert, and as the king has ridden a month to come to Eddard for help, it is obvious that he is the only one that Robert trusts. Catelyn insists that Eddard owes Robert nothing, having spent half of his life fighting in Robert's wars. Catelyn reminds Eddard that his father and brother once rode south to answer the call of a king, but Luwin believes the circumstances to be different. Eddard listens with intense concentration as they debate.
When Robert arrives, he does indeed ask Eddard to be his Hand, and offers a contract of marriage between his heir, Prince Joffrey, and Eddard's daughter Sansa. Eddard asks for time to consider. Sansa is overjoyed, as she believes herself to be in love with the young prince; she begs her parents to agree. Together, Lord and Lady Stark host the feast held at Winterfell to welcome the royal party. The next day, as King Robert is on a hunt, Bran is climbing an unused tower, when he witnesses the incestuous and adulterous affair of Cersei and Jaime Lannister. Jaime Lannister pushes him from the window, in order to protect their secret. Bran survives the fall, but lapses into a coma.
A Bitter Parting
A distraught Catelyn sits at Bran's bedside. Eddard stands at the door and witnesses his wife telling Jon Snow to leave. Jon had come to say farewell to Bran. After Jon exits, Eddard closes the door and comes to sit next to her. She reminds him of how he rode away from her 17 years before, only to return with another woman's child. Now he is abandoning her again. When he says that he has no choice, she replies that this is a common excuse that men use when honor calls. He is leaving his family and her in a time of turmoil, and he has chosen to do so. As he reaches for her hand she pulls away. She tells him that she cannot face this alone, but he says that he has faith that she can and that she must. She is crying as she watches him leave the room. Eddard accepts the position of Hand of the King and travels to King's Landing, taking his two daughters Sansa and Arya with him.
Catelyn tends to Bran after he falls from a tower. Her refusal to leave Bran's side starts to cause problems for the smooth running of the castle. An assassin tries to kill Bran, but Catelyn holds the assassin off long enough for Bran's direwolf to enter the chamber and tear out his throat. The next day, Catelyn goes to the tower from which Bran fell and finds a blonde strand of hair inside. She tells Robb, Luwin and Ser Rodrik Cassel, the Master-at-Arms, that she suspects that the Lannisters tried to kill Bran, because he saw something in the tower. Catelyn decides that Ned must know the truth and resolves to meet him in King's Landing. Ser Rodrik escorts her, whilst Robb commands the castle in her absence. 
Catelyn Stark and Ser Rodrik arrive at King's Landing and attempt to sneak into the city, but they are spotted by one of Petyr Baelish's men. He serves as King Robert's Master of Coin. They are taken to meet Littlefinger at a brothel he owns. Catelyn is angered by the way they've been treated, and for being brought to such a place. But Littlefinger asks her to consider the fact that who would think to look for Lady Catelyn of Winterfell in a brothel. However, Lord Varys has not been fooled. One of his "little birds" has informed him of her presence. Catelyn asks Petyr to aid them in finding the people who tried to have Bran killed. Littlefinger tells them that he once owned the dagger that was wielded by the assassin, but that he had recently lost it to Tyrion Lannister, betting on the outcome of a joust between Jaime Lannister and Ser Loras Tyrell. 
Petyr Baelish tells Eddard Stark that his wife is in King's Landing; Eddard goes with him, even though he suspects that it is a trick. When Petyr takes him to a brothel and tells him that Catelyn is inside. Eddard grabs Baelish by the front of his robe and pushes him up against the wall of the brothel. He accuses Littlefinger of playing a sick joke and asks him what his game is. Just then, Catelyn appears on the balcony above them and tells him to stop. A dumbfounded Eddard drops his hands from around Petyr's throat and enters the brothel. Littlefinger, rubbing his neck, mutters that the Starks have quick tempers and little minds.
Littlefinger tells them that charging Tyrion with the crime may be viewed as treason as they would be accusing the Queen's brother. The evidence of the knife will not be enough to condemn him, as he could always say that the knife was stolen. The only one who could corroborate the evidence is the assassin who is dead. Catelyn encourages Eddard to place his trust in Petyr Baelish, as he is like a little brother to her and would never betray her. Baelish promises, for Catelyn's sake, to protect Eddard in the turmoil that is to come. Catelyn assures him of her gratitude and calls him a true friend. Littlefinger tells her to keep that a secret as he has a reputation to maintain.
Ned and Catelyn stand in a small courtyard. Ser Rodrik stands apart from them holding the reins of the horses. She regrets that she couldn't see the girls while in King's Landing, but Eddard says that it was too dangerous. Despite Catelyn's certainty that the Lannisters are responsible, he says that they still don't know who their enemies are, and until he has proof, he cannot go to Robert. He only hopes that Robert is still the man he once knew and will support his claim for justice. He asks Catelyn to be careful on the road and chides her on her temper. She counters that her temper is not as bad as his, and they laugh recalling how he assaulted Petyr Baelish outside the brothel. Eddard has realized that Petyr Baelish still loves Catelyn, but she dismisses it as unimportant. They stare into each other's eyes and then passionately kiss. As before, he doesn't say goodbye, he just says, "Off with you". But as she goes, he looks at her with trepidation, perhaps knowing that it is the last time he will ever see her. She rides through the archway after Ser Rodrik without looking back.
Littlefinger is helping in Eddard's investigations into the death of Jon Arryn: giving him leads, advising him on how to proceed, and informing him about spies. He tells him to trust no-one. Eddard remarks to Lord Baelish that perhaps he was wrong to have at first mistrusted him. However, a smiling Littlefinger tells him that mistrusting him was the wisest thing that Eddard had done since he arriving in the capital.
Catelyn Stark meets Tyrion Lannister at the Crossroads Inn, when she is on her way back to Winterfell. Spontaneously, she decides to take him prisoner and deliver him to the Eyrie to face justice. Eddard Stark learns of his wife's actions, but protects Catelyn by insisting that these actions were carried out under his authority and that she was only obeying his instructions as King's Hand.
Eddard Stark has discovered that Robert's heirs: Joffrey, Myrcella, and Tommen are not his, but are the products of Cersei's adulterous relationship with Jaime. When confronted by Eddard, Cersei proudly admits this to be true. Eddard warns her to flee the capital with her children, before he tells Robert the truth, as he fears Robert will order them all killed. Cersei tells Eddard that he should have seized the throne for himself after the sack of King's Landing. Eddard says that he has regrets in his life, but that isn't one of them. 
Rememberances of Things Past
Petyr Baelish in his brothel talks to Ros saying that he has only ever had eyes for one woman and is saving himself for her. When she comments that this woman must be very beautiful, Littlefinger tells her that she is not particularly, but that her bloodlines are impeccable. He tells them about his past, how for many years he loved a woman, and she loved him in return. She saw him as a confidant and a plaything. However, she was destined to marry a northerner, whom Littlefinger describes as having a jaw like an anvil. Petyr Baelish challenged him to a duel, expecting to win the battle and the girl, as in a romantic story. He not only failed to win, but the woman he loved had to step in to plead for his life to be spared. She said that he was just a boy. Littlefinger still carries the scars. When this northerner died she came to marry his brother, who was even more impressive. She even came to love this man, as he was so very good. Petyr Baelish tells Ros that subsequently he realized that he could never beat those in power by honorable means, playing their game by their rules, as they would never let him compete on equal terms. When Ros asks him what he wants, he says, "Oh, everything."
At King's Landing, King Robert has been badly mauled by a boar and is not expected to survive. Eddard chooses not to tell Robert about his discoveries to spare his final hours from pain. Robert instructs Eddard to take a letter naming him as the Lord Protector of the Realm, to rule as regent. Lord Eddard tells Littlefinger the truth about Joffrey's parentage. Petyr advises him to support Joffrey, but to threaten him with the truth, so he will be controllable. If that fails, they can support Renly Baratheon's claim. Eddard calls this treason and is determined to give the throne to Stannis Baratheon, the elder of Robert's younger brothers. Littlefinger agrees to help, but tells Lord Eddard that even though he has Robert's edict naming him Regent and Protector of the Realm, Eddard doesn't have the men he needs to seize control from Cersei. He needs the loyalty of the City Watch. Littlefinger understands that the honorable Eddard Stark can't come right out and ask him to bribe them, but says that he will do what needs to be done.
The next morning, Eddard is summoned to the throne room by "King Joffrey"; Robert has died. He arrives to find Littlefinger and Varys, the Master of Whisperers, waiting for him, along with Commander Janos Slynt and a detachment of the City Watch. Joffrey demands oaths of fealty from his councilors and subjects. Instead, Eddard gives the proclamation naming him as Lord Protector of the Realm to Ser Barristan Selmy to read aloud. To Barristan's shock, Cersei tears it up, and suggests that Eddard bend the knee and swear allegiance. In return, he will be allowed to return to Winterfell. Eddard responds that Joffrey has no claim to the Iron Throne and commands Slynt to take the queen and her son into custody. Instead, the City Watch kill Eddard's bodyguards, and Littlefinger himself holds a knife to Eddard's throat, saying, "I did warn you not to trust me."
When word of Lord Eddard's arrest on the charge of treason reaches Winterfell, Robb Stark calls up his bannerman and goes to war on the forces of the Lannisters. He takes Jaime Lannister prisoner, after the Battle of the Whispering Wood.
Varys visits Eddard in the dungeons. He blames Eddard for Robert's death, as Eddard trusted Littlefinger and warned Cersei. He informs Eddard that though Arya escaped, the Lannisters hold Sansa hostage. He advises Eddard to confess to treason and accept being sent to the Wall. If it was only a question of his own life, Eddard would hold to his honor and die proclaiming Joffrey as a false heir, but this is the only way he can ensure Sansa's safety. Lord Eddard is taken to the Great Sept of Baelor for public trial, and, even though he confesses to treason and acknowledges Joffrey's claim to the throne, he is executed.
Word of Lord Eddard's execution has reached Robb Stark's camp. A withdrawn Catelyn Stark walks through the camp, while the men of the Stark forces bow to her, showing respect and condolences. She walks into the surrounding wood and, once concealed, collapses against a tree to weep. Hearing noises from further in the forest, she walks on to find Robb crying as he angrily strikes his sword repeatedly against a tree. She calls to him and gently points out that he is ruining his sword. Robb drops the sword and falls into his mother's arms. He wants to kill the Lannisters for what they have done. Lady Catelyn reminds him that they still have Sansa and Arya. After they free the girls, then they may "kill them all." ____
Renly Baratheon has raised an army and seeks to take the throne from King Joffrey. Petyr Baelish meets with Catelyn Stark in her tent in Renly's camp. She is upset at his betrayal of her husband and confronts him with angry recriminations. He says that he wanted Eddard to serve as protector of the realm and begged him to seize the moment. But Catelyn rightly believes that he repaid their faith in him with treachery, abandoning Eddard to his death, and she orders Petyr out. Baelish then tries to kindle a romance with her, now that they are both free, it may be that they can be together. He tells her that he loves her and tries to take her arm. Catelyn grabs a knife and tells him to back off. So he moves on to present Tyrion's offer that the Lannisters want to make a prisoner exchange with the Starks: if they release Jaime Lannister, Queen Cersei will release both Sansa Stark and Arya Stark. He asks if she wants to see her daughters and says that Sansa is growing more beautiful, while Arya is just as wild. Catelyn asks if they truly have Arya, and he repeats the lie, claiming that he is concerned for them if they remain captives of Cersei and Joffrey. Catelyn puts down her weapon and asks what he wants. He says that the Lannisters would trade her daughters for Jaime. Catelyn insists that Robb would never allow the exchange, but Littlefinger tries to manipulate her love for her imprisoned daughters. He suggests that she consider the terms on her own, as a mother.
He says that he has a gift to show Tyrion’s goodwill, Baelish brings forward a pair of Silent Sisters. They enter the tent carrying a chest. Catelyn asks what it is, and Petyr is silent as she deduces it for herself. She kneels and opens the chest. Petyr says that Eddard was an honorable man and deserves burial with his family in the crypts of Winterfell. The box contains the returned bones of Ned Stark. Deeply grieving with her voice choked with emotion, Catelyn tells Petyr to get out. When she is alone with Eddard’s remains, she allows herself a moment to cry and look at the bones with pain, but then she shuts the box with a look of resolve on her face.
Robb talks to his mother about his intention to marry Talisa. Catelyn tells him that she and Eddard Stark were strangers when they married and yet came to love passionately. Love didn't just happen to them, they built their love stone by stone, over the years, and not just for themselves, but for the benefit of their children. It is not exciting like secret passion in the woods, but what they would have would be stronger. She reminds Robb that he agreed to it, that he gave his word, and if he treats his oaths recklessly, then his people will do the same. She even starts to bring up his father and what Eddard lived his life for (honor, duty, fealty). However, Robb in the flush of first love won't listen. 
|Season One appearances|
|Winter is Coming||The Kingsroad||Lord Snow||Cripples, Bastards and Broken Things||The Wolf and the Lion|
|A Golden Crown||You Win or You Die||The Pointy End||Baelor||Fire and Blood|
|Season Two appearances|
|The North Remembers||The Night Lands||What is Dead May Never Die||Garden of Bones||The Ghost of Harrenhal|
|The Old Gods and the New||A Man Without Honor||The Prince of Winterfell||Blackwater||Valar Morghulis|