Brienne travels towards Maidenpool with Podrick, whom she is trying to teach how to be a proper squire and how to fight. They come across a cart being pulled by a farmer and his wife and fall in with them. The man says they had an ox before the war, but it was taken by Northmen. His daughter was also carried off, but she wandered back later. He says that Lord Randyll has rebuilt much of Maidenpool and has hunted down and killed many of the worst outlaws. She asks them about Sansa, but they have not seen her. They are bringing eggs for the wedding that is about to occur of Lord William's daughter and Randyll's son, Dickon. Brienne thinks of how she was betrothed to Lord Caron's younger son when she was seven and he was ten before a chill claimed his life and those of his mother and father. When they arrive at Maidenpool, the guards try to steal the eggs and rape the farmer's wife. Brienne tries to stop them, but they surround her and prepare to attack. Ser Hyle Hunt appears from the gatehouse and puts an end to it. He follows her into the city, mocking her all the while. He asks what her business is and she tells him that she is looking for a man at the Stinking Goose. He tells her where the inn is, but then insists that she see Lord Randyll first. As they pass through the town, Brienne sees signs of rebirth everywhere. Lord Randyll has his soldiers rebuilding the town, and traders are returning to the harbor. She decides that if the Stinking Goose yields nothing she will take a ship to Gulltown and make for the Eyrie. They find Lord Randyll with Lord William in the harbor dispensing justice before a long gallows where several corpses are already hanging. After deciding several more cases, Lord Randyll turns his attention to Brienne and demands to know what she is doing there. Brienne, greatly intimidated by the man, hands him Tommen's order and admits she seeks Sansa. Lord Randyll says she is not there and probably fled North. Brienne reveals the possibility of the Vale, but Randyll tells her of Lysa's death. Lord Randyll gives her leave to go where she will. Hyle offers to lead her to the Stinking Goose, but Brienne declines. Hyle tries to apologize to her for some past act, and tells her that Big Ben Bushy, Richard Farrow, and Will the Stork died on the Blackwater and Mark Mullendore lost half his arm. She turns her back on Hyle and walks off.

Brienne orders Podrick to stable the horses while she goes to the Stinking Goose. Podrick asks if she knows where it is and wonders why she did not let Ser Hyle take them there when she answers in the negative. She tells him that Hyle and some other men with her played a cruel and hurtful game with her when Renly called his banners. It takes Brienne an hour to find the Stinking Goose, which is unkempt and putrid. She asks the proprieter about Nimble Dick. The woman tells her his name is Dick Crabb and that he comes in most nights. Brienne gives the woman a copper to give her a nod when Dick comes in that night and then takes a seat. As she sits, she thinks on how she has no idea now how to find Sansa. She also thinks back to Renly's calling of the banners. She had expected hostility and mockery when she showed up in her armor, but was surprised at the kindness of a select few. Big Ben sent his squire to clean her mail and giften her a drinking horn, Ser Edmund Ambrose brought flowers and went riding with her, Ser Hyle brought a beautifully illuminated book and sundry other gifts, Ser Richard played love songs on his lute, Ser Hugh Beesbury brought her a pot of honey, Ser Mark made her laugh with the antics of his monkey, and Will the Stork offered to rub her shoulders. She refused them all, and when Ser Owen Inchfield attempted to kiss her, she knocked him backwards into a cookfire. Brienne was perplexed by the behavior until Lord Randyll summoned her. Dickon had overheard four knights laughing about a wager they had. Apparently Ben, Edmund, and Hyle began a game to see who could claim her maidenhead, which soon spread to much of the camp. Each person had to pay a gold dragon to enter the contest, and the winner got the pot. Randyll put an end to the game and blamed Brienne for being there and acting like a camp follower. He strongly urged her to return to Tarth. Her reverie is interrupted by Dick's arrival. She buys him a glass of wine and pays him for information about the fool. He explains the man was there looking for passage for three, and Brienne thinks this might be Sansa and Arya.¹ He says he sent them to the Whispers, the ruined seat of Ser Clarence Crabb, which used to be a smuggler's cove but has not been used for thirty years. He agrees to lead Brienne there for six gold dragons.