Quando o Rei [[Robert Baratheon|Robert]] visita [[Winterfell]] e os [[Casa Stark|Stark]] lhe oferecem um banquete, Benjen se faz presente.{{Ref|AGoT|2}} Ele conversa com [[Jon Snow|Jon]], e o garoto diz que deseja se juntar à [[Patrulha da Noite]]; Benjen lhe diz para aguardar alguns anos até que tenha certeza, argumentando que [[Jon Snow|Jon]] é apenas um garoto, mas [[Jon Snow|Jon]] se irrita quando Benjen sugere que [[Jon Snow|Jon]] deve gerar alguns bastardos antes de se juntar a [[Patrulha da Noite]] e a conversa tem um fim ali. No entanto, Benjen aborda Meistre [[Luwin]] sobre Jon, informando o Meistre dos desejos de [[Jon Snow|Jon]]. Por sua vez, Meistre [[Luwin]] informando Lorde [[Eddard Stark]] que, a princípio se recusa, mas com alguma influência de [[Catelyn Tully|Catelyn Stark]] e Meitre [[Luwin]], Lorde [[Eddard Stark|Eddard]] concorda e envia Jon para se juntar ao [[Patrulha da Noite]]. {{Ref|agot|6}}
Benjen Stark lidera o grupo que se dirige para o norte até a [[Muralha]], com [[Tyrion Lannister]], [[Jon Snow]], [[Yoren]], [[Jyck]], [[Morrec]] e mais dois novos recrutas (dois estupradores). [[Tyrion Lannister]] não sente muita simpatia por Benjen Stark que fizera de tudo possível para que a viajem seja o mais desconfortável possível para o anão. Quando Benjen oferece uma pele para o anão (apenas por educação) ele pensa que Tyrion ia recusar, mas o anão aceita fazendo disso uma pequena vingança contra Benjen, dizendo que os Lannisters aceitam tudo que lhes é oferecido.{{ref|agot|13}}
De volta à [[Muralha]], Benjen se ocupa de seus deveres como [[Primeiro Patrulheiro]] e não tem muito tempo para dedicar a [[Jon Snow|Jon]]. Ele lembra [[Jon Snow|Jon]] que os irmãos juramentados deixam suas histórias, famílias e lealdades para trás quando fazem o juramento. {{Ref|aGoT|19}}