Quando foi procurar Sor [[Goodwin]] para que a instruísse, O Mestre de Armas afirmou que todo cavaleiro tem cicatrizes de batalha e perguntou se era isso que Brienne desejava. E assim começou seu treinamento.{{Ref|aFfC|42}} Sor [[Goodwin]] nota durante os treinos que ela era tão forte quanto a maioria dos cavaleiros e mais rápida que uma mulher do seu tamanho deveria ser e além disso era muito resistente e perseverante, o que era ótimo, pois frequentemente a vitória ia para o homem com mais resistência. Sor [[Goodwin]] afirma que os homens sempre vão subestimá-la e que Brienne deve tirar vantagem disso em batalha.{{Ref|aFfC|9}} Mas apesar disso, Sor [[Goodwin]] temia por ela ainda ter um coração de mulher. Para endurecê-la, mandou-a ao carniceiro para abater cordeiros e leitões e quando acabou Brienne estava cega com as lágrimas e tinha a roupa tão ensanguentada que a deu à aia para que a queimasse. Ainda assim as dúvidas de Sor [[Goodwin]] permaneciam.{{Ref|aFfC|20}}
Paralelamente ao seu treinamento, o pai de Brienne encontrou com três homens dispostos a desposá-la, pelas terras de seu pai. Um filho mais novo do Senhor [[Bryen Caron]] foi o primeiro pretendente de Brienne. Eles se encontraram apenas uma vez, por ocasião de seu noivado, quando tinha sete anos e ele tinha dez anos. O menino morreu dois anos depois de uma gripe, junto com seu pai, mãe e irmãs. Se ele não tivesse morrido, Brienne teria se casado com ele no ano de sua primeira floração.{{Ref|AFFC|4}} O segundo esconderijo foi Sor [[Ronnet Connington]], também chamado de Ronnet Vermelho, que era seis anos mais velho do que ela. Quando se encontraram pela primeira vez, Ronnet Vermelho lhe deu uma rosa, e disse-lhe que era tudo o que ela teria dele, e acabou com noivado.{{Ref|affc|27}} O último noivo/prometido de Brienne, Sor [[Humfrey Wagstaff]], que advertiu que ele deveria ser mais feminina uma vez que eles se casaram e parece de agir como um guerreiro. Mesmo com apenas dezesseis anos, Brienne respondeu que só aceitaria tal exigência de um homem que poderia vencê-la em combate. Sor Humfrey aceitou o desafio e acabou com três ossos quebrados e um casamento quebrado.{{Ref|AFFC|9}}
Depois disso, Lorde [[Selwyn Tarth]] desistiu de tentar arrumar um casamento para Brienne.{{Ref|AFFC|9}} A única experiência positiva que Brienne teve com um homem ocorreu quando o suserano do Senhor [[Casa Tarth]], Lorde [[Renly Baratheon]], visitou sua ilha de [[Tarth]] durante uma viagem. Ele se encontrou com Brienne e tratou-a com cortesia, e ela se apaixonou por ele.{{Ref|AFFC|4}} Algum tempo depois, Lorde [[Selwyn Tarth]] enviou-a para [[Ponta Tempestade]].{{Ref|ACOK|42}}