Catelyn and Ser Rodrik approach King's Landing on Storm Dancer, captained by Moreo Tumitus. Ser Rodrik has been sick for most of the voyage, and finally had to shave his whiskers after befouling them one too many times. Once ashore, they plan to contact Ser Aron Santagar, master-at-arms for the Red Keep, whom they hope can identify the dagger. Ser Rodrik emphasizes the need for secrecy and that there are those at court who would recognize Catelyn on sight. Catelyn realizes he means Littlefinger, Lord Petyr Baelish. He had been a ward to Catelyn's father and a brother to Catelyn herself. He wanted more than that, however, and when he learned that Catelyn was to marry Brandon Stark, he challenged the older man to a duel. Brandon was twenty, Petyr scarecely fifteen, and there was no hope that he could prevail. Catelyn begged Brandon to spare his life, so he left Petyr with only a scar. Catelyn's father sent him away after that. He wrote Catelyn a letter after Brandon was killed, but Catelyn did not read it. Rodrik mentions that Petyr is now on the small council, and Catelyn responds that she always knew he would rise high. They decide that Ser Rodrik will go to the castle and fetch Ser Aron while Catelyn waits for him in a safe place.

Upon going ashore, Catelyn and Ser Rodrik choose an inn recommended by Captain Moreo, and Ser Rodrik departs for the Red Keep. Catelyn falls asleep and wakes to pounding on her door. She opens it to discover men of the City Watch who are under orders to escort her to Lord Petyr. When she arrives, Petyr informs her that he learned of her arrival from Lord Varys, who will join them shortly. Varys went to Petyr because he is master of coin, and most of the small council is gone, with Ser Barristan and Lord Renly off escorting King Robert and Lord Stannis gone to Dragonstone. Also, Varys knew that Petyr was friends with Lysa. Petyr asks why Catelyn is there and is not convinced by her explanation that she wanted to see her husband, as the Tully words are "Family, Duty, Honor," and Catelyn would never leave her assigned post. Varys arrives and asks after the dagger, which he discovered through the "whispering of little birds" after Ser Rodrik met with Ser Aron, both of whom left the castle and are waiting for Catelyn at the inn.¹ She pulls the dagger out, and Petyr reveals it was his until he lost it at the tournament held on Prince Joffrey's name day when Ser Loras Tyrell unhorsed Ser Jaime Lannister. He says he lost the dagger to Tyrion Lannister.²