tl; dr: Até o momento, não temos informações sólidas sobre de onde os Outros (que são chamados White Walkers na TV, para evitar confusão com o termo geral "outros") vieram. Também não sabemos muito sobre o Rei da Noite, mas ele definitivamente não foi o primeiro Caminhante Branco, já que eles antecederam a Patrulha da Noite.
Infelizmente, não há registros realmente confiáveis de nada isso aconteceu durante esse tempo, pois a história escrita não começou até 6,000 BC com a chegada dos Andals. Em vez disso, a história foi passada de boca em boca, através de histórias que se tornaram mitos e lendas. Isso significa que nossa fonte de informação mais "confiável" vem de pessoas como a Old Nan. Enquanto Nan tende a estar certa sobre muitas coisas, suas informações ainda são anedóticas e até agora, e ela está mais interessada em ter boas histórias do que bons fatos, por isso devemos ser céticos em relação ao que ela tem a dizer.
Os Outros e a Longa Noite
Os Outros apareceram pela primeira vez em torno de 8,000 BC (Antes da Conquista - antes do início do reinado de Aegon I Targaryen), o que o coloca bem no meio da Era dos Heróis. (Para referência, os Primeiros Homens chegaram a Westeros por volta de 12,000 BC, e fizeram as pazes com os Filhos da Floresta por volta de 10,000 BC). Naquela época, os Primeiros Homens e as Crianças estavam em paz, e muitas das Grandes Casas estavam apenas começando. Todos os ancestrais lendários das casas atuais viveram durante esse período - Bran, o Construtor, Lann, o Inteligente, o Rei Cinzento das Ilhas de Ferro, etc.
Cerca de 2,000 anos depois que o Pacto foi assinado entre os Primeiros Homens e as Crianças, Westeros passou por um longo inverno sem precedentes, colocando Westeros em muito mau estado. No meio deste inverno, houve uma catástrofe ainda pior: a Longa Noite, na qual o sol não nasceu durante uma geração inteira (o que provavelmente significa pelo menos anos 20). Foi durante essa longa noite que os Outros apareceram, dos extremos extremos do norte de Westeros.
O clima no extremo norte é semelhante ao da Antártica, e pensava-se que era completamente impopular. Assim, a aparição de Outros foi uma surpresa completa. Novamente, não sabemos ao certo, mas parece que eram algo novo para Westeros, pois os Filhos da Floresta não sabiam como derrotá-los. Os Outros empurraram para o sul de Westeros antes que sua fraqueza - obsidiana - fosse descoberta e eles foram empurrados para trás.
A Patrulha da Noite e o Muro
A Patrulha Noturna foi formada durante esse período, especificamente para combater os Outros. (Esta parte da história é comemorada em uma música, "The Night That Ended", que é cantada no norte e referenciada algumas vezes, embora, como este não seja Tolkien, não obtemos nenhuma letra :(). Watch lutou contra os Outros e finalmente os derrotou na Batalha pelo Amanhecer.
Depois disso, Bran, o Construtor, e seus aliados construíram The Wall, novamente especificamente para lutar contra Os Outros. Era para garantir que eles nunca pudessem se aproximar de Westeros novamente. A Patrulha da Noite, sendo os que sabiam como combatê-los, estava destinada a enfrentar o Muro.
Novamente, não há histórias escritas de nada durante esse período, por isso não sabemos os nomes dos comandantes. Somente aqueles que fizeram algo digno de música ou história são lembrados.
O rei da noite e sua noiva
O rei da noite foi a décima terceira pessoa eleita como o senhor comandante da guarda. Segundo sua lenda, ele abandonou seu Juramento, tomou uma noiva e levantou a Patrulha da Noite em rebelião contra Westeros. Sua noiva é descrita como:
with skin as white as the moon and eyes like blue stars
Dada essa descrição, é óbvio por que muitos fãs assumem que ela é uma Outra, embora os meistros do universo aparentemente pensem que sua descrição corresponde à dos homens e mulheres das Barrowlands. Em ambos os casos, sabemos quase nada sobre eles pessoalmente. Sabemos que ele acabou sendo derrotado pelo rei no norte e pelo rei além do muro. Sabemos que ele acabou descobrindo que estava fazendo sacrifícios para Os Outros (como Craster), e que todos os registros possíveis de seu nome foram destruídos, e as histórias e músicas subsequentes usam apenas seu apelido.
Mais por vir
Martin tem sido muito intencionalmente tímido em revelar informações sobre coisas de origem mágica. (por exemplo, consulte A ponte sobre o rio Rhoyne para um caso em que ele cortou algo porque era potencialmente "muito mágico".) No entanto, ele também disse que acabará revelando muito disso, no final da série. Ele também disse que aprenderemos mais sobre os Outros (embora ele não tenha prometido que aprenderemos onde eles veio de) no próximo romance.
Martin sugeriu que o clima desagradável em Westeros é de natureza mágica, e os Outros também são claramente sobrenaturais. Eles também parecem estar extremamente intimamente relacionados - as duas vezes em que apareceram foram durante o que era supostamente um inverno extremamente severo. Portanto, é muito provável que suas origens estejam intimamente ligadas, e descobriremos sobre os dois ao mesmo tempo.