Antes de morrer, [[Timeon]] afirma para Brienne que [[Sandor Clegane]] andava com um [[Arya Stark|uma das filhas da Senhora Stark]] e que andava em direção a [[Correrrio]]. {{Ref|AFfC|20}} Seguindo as informações do mercenário, Brienne volta para o [[Terras Fluviais]] para encontrar [[Sandor Clegane]] e [[Sansa Stark]], mas Brienne não sabia que, na verdade, [[Sandor Clegane|Cão de Caça]] estava com a [[Arya Stark]] e não com [[Sansa Stark|Sansa]]. Em [[Lagoa da Donzela]] eles se juntam a [[Meribald]], um septão andarilho, que os acompanha para [[Salinas]]. A partir daí, ela visita a [[Ilha Quieta]], onde [[Irmão Mais Velho]] afirma com convicção que o [[Sandor Clegane|Cão de Caça]] está morto. {{Ref|AFFC|31}}
Na [[Estalagem da Encruzilhada]], perto do [[Tridente]], Brienne encontra com outro grupo de remanescentes da antiga companhia mercenária chamada [[Bravos Companheiros]], liderados por [[Rorge]], que está disfarçado de Sandor Clegane (usando seu elmo) e espalhando o terror pelas [[Terras Fluviais]]. Tentando defender os órfãos na [[Estalagem da Encruzilhada| pousada]], a Brienne mata Rorge, mas está em uma grande desvantagem numérica e acaba gravemente ferida por [[Dentadas]], que quebra seu braço e mastiga e engole a carne de seu rosto. {{Ref|AFfC|37}} mas no último instante [[Gendry]] atravessa a cabeça de [[Dentadas]] com uma lança e, ao lado da [[Irmandade Sem BandeiraBandeiras]] salva Brienne e os órfãs da [[Estalagem da Encruzilhada]], mas levam ela junto com [[Podrick Payne]] e Sor [[Hyle Hunt]]. {{Ref|AFFC|42}}
A [[Catelyn Tully|Senhora Coração de Pedra]] não acredita no relato de Brienne sobre sua busca para encontrar [[Sansa Stark]] e julgam que ela é uma traidora que serve [[Casa Lannister]], por vários motivos, dentre eles a [[Cumpridora de Promessas|sua espada]] e do Pergaminho Real. É imposto sobre Brienne a escolha de matar o [[Jaime Lannister| Regicida]] e provar sua lealdade ou ser enforcada por trair [[Catelyn Tully]]. Brienne se recusa a escolher e é condenado a forca, junto com seus companheiros. Mas quando viu que o pobre [[Podrick Payne]] também morreria por sua culpa, ela fala uma última palavra {{Ref|AFFC|42}} De acordo com uma fonte semi-canônica, ela vê Podrick sufocando e grita "espada", escolhendo, assim, matar Sor [[Jaime Lannister]]. <ref group ="N">[http://www.westeros.org/Citadel/SSM/Entry/6425/ So Spake Martin: MISCON REPORT (JUNE 03, 2012)]</ref>