Brynden é cinco anos mais novo que seu irmão, o Lorde [[Hoster Tully]], e foram muito próximos na infância. Após ser escudeiro do Lorde [[Casa Darry|Darry]], Brynden tornou-se [[cavaleiro]], e, durante a Guerra dos Reis de Nove Moedas, deixou [[Correrrio]] com muitos outros para lutar contra o [[Bando dos Nove]]. Ele lutou ao lado de figuras como Sor [[Barristan Selmy]] da [[Guarda Real]], e provou seu valor como cavaleiro, ganhando fama e renome pelos [[Sete Reinos]].
Quando retornou, sua relação com seu irmão tornou-se tensa, após Brynden recusar-se a casar com uma [[Bethany Redwyne|senhora]] que Hoster escolhera para ele, para aumentar as fortunas da família. Isto causou anos de discussões desagradáveis e distanciamento. Após uma destas discussões com seu irmão mais velho, quando foi chamado por ele de "''a ovelha negra do rebanho Tully''", Brynden apontou que o símbolo deles era um peixe, então ele assumiu o nome ''Peixe Negro'' e mudou seu brasão para uma truta preta negra saltante. {{ref|agot|34}}
Sem esperança de reconciliação após a [[Rebelião de Robert]], ele acompanhou sua sobrinha [[Lysa Tully]] ao [[Vale de Arryn]], onde serviu à [[Casa Arryn]]. Em retribuição aos anos de serviço leal, Lorde [[Jon Arryn]] o nomeou Cavaleiro do Portão, uma posição de grande honra no [[Vale de Arryn]]. {{ref|agot|2}}