- "Thousands of years ago, there came a night that lasted a generation. Kings froze to death in their castles, same as the shepherds in their huts; and women smothered their babies rather than see them starve, and wept, and felt the tears freeze on their cheeks... In that darkness the White Walkers came for the first time. They swept through cities and kingdoms, riding their dead horses, hunting with their packs of pale spiders big as hounds."
- ―Old Nan to Bran Stark
Eight thousand years before the Targaryen Conquest, a winter known as the Long Night descended upon the world, which lasted an entire generation. Thousands starved as the crops and fields lay buried under dozens of feet of snow. In the darkness and cold of the Long Night, the White Walkers descended upon Westeros from the furthest north, the polar regions of the Lands of Always Winter.
The War for the DawnEdit
None knew why the White Walkers came, nor their nature and origins, but they killed all in their path. The White Walkers reanimated the dead as Wights to kill the living at their command, and soon the White Walkers led their hordes of undead to sweep across the continent.
Eventually the First Men and the Children of the Forest rallied to defend themselves and in a conflict known as the War for the Dawn, the White Walkers were defeated and driven back into the uttermost north.
The Wall was constructed along the northernmost isthmus of northern Westeros to bar their return, a massive fortification standing seven hundred feet high and stretching from one side of the continent to the other. Legend says that the Wall was infused with powerful magic spells by the Children of the Forest that prevent the White Walkers from crossing it. The ancient order of the Night's Watch was founded to defend the Wall.
In the present day, most believe that the Long Night is just a children's story, and that the White Walkers are nothing more than legends. Even the few who believe they did once exist think they went extinct thousands of years ago. Certainly, none were seen for the next eight thousand years between their supposed defeat and the time of Robert's Rebellion.
As the War of the Five Kings begins, disturbing reports have come back from the scouts of the Night's Watch that for reasons as yet unknown, the White Walkers have begun to return. Given that the great lords of Westeros are short-sightedly more concerned with fighting each other for control of the realm, most have simply ignored the warnings of the Night's Watch, to focus on their civil war. This leaves only the under-supported and under-manned Night's Watch to stand between the White Walkers and the realms of men.
During Stannis Baratheon's march to Winterfell, the weather turns for the worse and a snow storm delays his army. Melisandre speaks alone with Stannis and reminds him that they may need to sacrifice more King's blood in order to better their chances of winning the upcoming battle in the snow which they both saw in the flames, citing the deaths of Robb Stark and Joffrey Baratheon as examples. When Stannis says that they have no chance of locating Gendry, Robert Baratheon's bastard son, Melisandre suggests that they sacrifice Stannis' daughter, Shireen. Stannis is visibly shocked and disgusted by the suggestion, asking her if she has lost her mind. She tries to convince him by saying that Stannis must be the undisputed king when the the Long Night comes, but he rebuffs her and orders her to leave his presence.
In the booksEdit
As of the fifth novel in the A Song of Ice and Fire series, A Dance with Dragons, very little detail has been given about what actually happened in the War for the Dawn. Written history doesn't date back that far, so only oral tradition and half-mythical accounts come down to the present. There are vague legends that a single First Man that Old Nan refers to in her stories as "the last hero" unified both the First Men and the Children of the Forest and led them to victory. According to Melisandre, there are also stories and legends of the Long Night in Essos. They refer to the "last hero" as "Azor Ahai". According to prophecies in the holy books of the Lord of Light's religion, there will come a time of darkness when the White Walkers return, and Azor Ahai will be reborn to lead the people of the world to defeat them again.