The beginning of time, but not recorded history, in Westeros was known as the Dawn Age (I: 616). This time period, of indeterminate length, found Westeros populated by the children of the forest, who for time-uncounted lived alone throughout the continent of Westeros, except perhaps for the giants (and maybe one other race, if the legend of the Seastone Chair on Old Wyk in the Iron Islands is true (II: 287)). They worshipped the gods of forest and stream and stone whose names were secret (I: 617).
No one knows how long it was that the children lived alone in Westeros, nor where they themselves came from. We do know, however, when they came in contact with the first outsiders. This was about 12,000 years ago, and these invaders were the First Men (I: 617).
The First Men crossed into what would be Dorne from the eastern continent, using the land bridge that connected the continents. The children shattered this land-bridge in a futile attempt to end of the invasion (I: 498, 617), the result being the Broken Arm of Dorne and the chain of islands named the Stepstones (SSC). The First Men brought with them bronze, great leathern shields, and the first horses. They also brought their own gods, but these they eventually put aside for the gods of the children (except in the Iron Islands, where the religion of the Drowned God was invented (SSC). They warred with one another at first, as the children fought the First Men for cutting down and burning the weirwoods to clear land for themselves. The First Men continued to cut them down after this, but for fear that the children could watch them through the eyes of the carved trees (I: 617).
After centuries of fighting, when it seemed all was going in favor of the First Men, a peace was forged (which we speculate to have happened 10,000 years ago, roughly in the same period as the raising of Moat Cailin (II: 674)). The Pact was commemorated at the Isle of Faces, where every weirwood was carved with a face and they were all guarded by the order of the green men. The Pact began 4,000 years of friendship between men and the children, and ended the Dawn Age to begin to the Age of Heroes, during which times legendary figures such as Lann the Clever and Brandon the Builder were reputed to live. The Pact gave the coasts, high plains, meadows, mountains, and bogs to the First Men. In turn the children were given the deep forests, and the promise that no more weirwoods would be cut down (I: 617).
The Pact survived even the Long Night (I: 618), which took place some 8,000 years ago (I: 547). In this time night seemed to last for a generation, and there was terrible cold. The Others came from the cold landscape in the far north and nearly destroyed all men in the Seven Kingdoms. The Long Night was ended at the Battle of the Dawn (II: 242) when the Night’s Watch rode out to face the Others and defeated them. The Wall was raised at this time (I: 37), reputedly with the aid of giants and the legendary Brandon the Builder (III: 461). Brandon the Builder is also said to have given the Night’s Watch "Brandon’s Gift", a stretch of land 25 leagues wide, but maesters argue it was some other Brandon (III: 452, 453).
Possibly related to the Long Night and the founding of the Night’s Watch is the apparent founding of the Stark line (II: 552), with Brandon the Builder as part of the line (and perhaps even its founder) (I: 678). It is suggested that Winterfell itself is some 10,000 years old (I: 18), but this is likely an example of the Westerosi penchant for rounding roughly and we speculate that the raising of Winterfell began more or less at the same time as the beginning of House Stark. For many thousands of years the Starks were not the uncontested Kings of the North, and their primary antagonists the Boltons of the Dreadfort did not bend the knee until some 1,000 years ago (II: 530).
A notable event in the millennia of service of the Night’s Watch is the rule of the 13th Lord Commander of the Night’s Watch, known now only as Night’s King after all records of his name were destroyed. He had bedded a strange, pale "corpse woman" and proclaimed himself a king and her his queen. Terrible things were done at the Night Fort by his Sworn Brothers, who were enslaved with sorcery. For thirteen years he ruled this way until the Stark in Winterfell and the King-beyond-the Wall Joramun joined forces to defeat him (III: 629, 630). This same Joramun was reputed to have sounded the Horn of Winter, waking giants from the earth (II: 276).
During the Age of Heroes the Seven Kingdoms were supposed to have first been founded (I: 618). According to legend, Lann the Clever winkled Casterly Rock from the Casterlys (I: 231) and reputedly the kings of the Rock claimed descent from him even into the modern era (I: 680). Similarly the most famous king of the Reach was Garth Greenhand, from whom the ruling House Gardener (and many other houses besides) claim their descent (I: 686. III: 67). In the stormlands the Storm Kings arose, a line founded by Durran who supposedly constructed Storm’s End to withstand the fury of the gods of the sea and the wind, who hated him for marrying their daughter (II: 345). In the Iron Islands, the Grey King reputedly married a mermaid and ruled not only the western isles but the sea itself (I: 687).
Approximately 6,000 years ago (I: 360) , the Age of Heroes and the peace of the Pact ended when the Andals invaded from across the sea, landing in the Vale (III: 770) and bringing a new religion and steel with them (I: 432, 617-618). For centuries they warred with the First Men until the six southron kingdoms fell to them and they destroyed all the weirwood groves and killed the children of the forest wherever they could find them. The children of the forest may have hidden themselves beyond the Wall at this point, and were supposedly never seen again (I: 209). Only the Kingdom of the North remained ruled by the First Men (I: 618), although Dorne seems to have been more a confederation of petty lordships than a proper realm given what is said about Mors Martell defeating his rivals for sole rule (I: 690). The Seven of the Andals may be the reason that slavery has not existed on the Westerosi mainland for thousands of years (III: 264), although the ironborn practice it with their thralls and salt wives (II: 124, 132) and the wildlings still keep thralls beyond the Wall (II: 458).
Among these fallen realms was that of House Mudd, who were Kings of the Rivers and Hills. They were the last of the First Men kings of the Trident and had ruled for 1,000 years before the Andals (III: 520. SSC). Perhaps one of the seven Andal kings who defeated and killed King Tristifer IV in his final battle was Erreg the Kinslayer who cut down the great weirwoods at High Heart and slew many of the children of the forest who tried to defend the ancient grove (III: 249). Elsewhere, the Andals established themselves as Kings of Mountain and Vale and from them descends House Arryn, one of the oldest lines of Andal nobility (I: 682), while Andal adventurers founded House Lannister and made themselves kings of the westerlands (I: 680) and Andals swept over the Iron Islands 4,000 years ago to end House Greyiron, the line of Urron Redhand which had ruled uncontested for 1,000 years (II: 137) but unlike in the other regions they were assimilated to the native beliefs of the Old Way and the Drowned God (I: 678).
Elsewhere in the world the eastern continent was dominated for the most part by the empire of Old Ghis which existed at a time when the Valyria in the Lands of the Long Summer (III: Map) was said to still be young and savage (III: 265). Five great wars were fought between Old Ghis and the Freehold (III: 307), wars which Valyria won with its dragons. At the last war some 5,000 years ago the Freehold finally conquered Ghis (III: 257). From here Valyria went on to conquer much other land as shown by the many straight roads (I: 193) that they made, although it seems to have focused primarily on coastal regions. The most westward holding of the empire was the cluster of islands about Dragonstone where they raised a citadel at an unknown time in the days of the empire (I: 692. III: 603).
The Nine Free Cities were clearly under Valyrian sway due to the bastard Valyrian they speak natively (I: 84), although Braavos, and perhaps others of the cities, did not exist at the time of the founding of the Valyrian empire (SSC). Interestingly, the Faceless Men have their origin in Valyria, although in a time prior to the existence of the Free City of Braavos (SSC). It is not impossible that this is related to the other major event so far written about: Azor Ahai and the prophecies about him.
It is not unreasonable to assume that Azor Ahai existed at about the same time as the Long Night, some 8,000 years ago, given the legend of his forging his sword to battle a darkness that was upon the world (II: 115). The fate of his Red Sword of Heroes and of himself is unknown, but it is said that he did win his war with the aid from others (III: 869). However, roughly at about the same time as the eclipsing of Old Ghis and the rise of Valyria, a prophecy dated to 5,000 years ago was made claiming that Azor Ahai would be reborn to save the world against a new darkness (III: 711).
At some point after the King-beyond-the-Wall Joramun there came other wildling kings, such as the Horned Lord and the brother-kings Gendel and Gorne (II: 276). 3,000 years ago the brother managed to evade the Night’s Watch and infiltrate the North in great numbers using a network of tunnels that extended under the Wall. With the aid of the King of the North and the Umbers the Watch was able to crush the wildling army, although the King of the North was killed by Gendel who in turn was killed by the new king. Wildling legend holds that Gorne and those who managed to escape the slaughter still wander the tunnels (III: 300).
Another notable King-beyond-the-Wall was Bael the Bard, who existed at some time when the Boltons were still hostile to the Starks. A song Bael wrote claimed that he seduced the daughter of the Stark in Winterfell and had a child by her, who grew up to be heir to his grandfather. The wildlings say that the son slew Bael in battle when he sought to break past the Wall. Never knowing that Bael was his father, he brought the head to Winterfell at which point his mother threw herself from the walls in grief at the kinslaying. His flaying at the hands of a Bolton was reckoned as the vengeance of the gods (II: 544-545).
The last major migration into Westeros would be the coming of the Rhoynar 1,000 years ago (II: 233). They were a people who lived in cities along the Rhoyne river on the eastern continent led by the warrior-queen Nymeria, and stories claim that Nymeria’s host were mostly women in a fleet of 10,000 ships (I: 59, 203. EHC). Taking Lord Mors Martell to husband, Nymeria gave him the strength to defeat all of his rivals and become the first Prince of Dorne (a title derived from the Rhoynar custom of not using king or queen). The Rhoynar married with the native people, leading to three distinct groups of Dornishmen living in the mountains, the deserts, and on the coasts (III: 430). The Rhoynar brought their own gods with them to Dorne, but they have largely disappeared in favor of the Faith. On the other hand, many Rhoynish customs, including inheritance regardless of gender, have been absorbed into Dornish society (EHC).
After this time no truly huge events happen until the Doom of Valyria approximately 450 to 500 years ago (I: 692. SSC: 86). The precise nature of the Doom is uncertain, but it was a cataclysm that destroyed the Freehold of Valyria and was powerful enough to shatter the Valyrian peninsula, leaving the strait through the ruin a smoking, demon-haunted place (III: 298). The survivors fled on ships to Dragonstone, where the Targaryens (descended from high lords of Valyria (I: 692)) took command and appear to have abandoned the old gods of Valyria in favor of the Seven (II: 109). Having few natural resources on Dragonstone, it is likely that they sold many valuable goods that they brought with them on the mainland, especially Valyrian steel swords, which are often dated to having been in Westerosi families for 400 to 500 years (I: 20, 225, 547). The only advantage they had over all other peoples in the world were the dragons that they had with them (I: 102).
Up to and after this time intermittent wars happened between Dorne and the kings of the Reach and the Stormlands (II: 233), and no doubt between many other realms (southron armies threw themselves at Moat Cailin for 10,000 years, for example (II: 674)). About 650 years ago the Storm Kings took control of the Trident up to the Neck (I: 684), Karlon Stark defeated sea raiders from the east and founded House Karstark some 1,000 years ago (III: 231, 232), and King Rickard Stark slew the Marsh King and married his daughter at some unclear date (I: 613). Also in this time, the Starks lost their strength at sea after Brandon the Burner burned his father’s fleet after King Brandon the Shipwright disappeared exploring the Sunset Sea (I: 613. II: 183). King Tommen II of the Rock went on a fool’s quest to Valyria and never returned, losing the Valyrian greatsword Brightroar (III: 359).
One of the major military forces in Westeros at this time were the kings of the Iron Islands, who terrorized all the western coasts. About 1,000 years ago an ironborn king butchered the captured sons of the River King, sending him the pieces (II: 133). In the time of King Qhored, Old Town, the Arbor, Bear Island (reputedly lost in a wrestling match to King Rodrik Stark, who gave it to the Mormonts (I: 613)), and many parts of the coast was under the control of the ironborn. His successors gradually lost many of these possessions over the centuries. Still, by the time of Harren the Black, 300 years ago, the ironborn controlled their isles and the whole of the Trident from the Neck to the Blackwater Rush after Harwyn Hardhand (Harren’s grandfather) defeated Arrec the Storm King and won the riverlands (I: 684, 688).
The only major event of note on the eastern continent so far, after the Doom of Valyria, was the coming of the Dothraki out of the Dothraki Sea. This took place 400 or more years ago and it can be assumed that the fall of Valyria and the chaos that followed it is what prompted (and perhaps allowed) the Dothraki to attack with such power. 50,000 Dothraki, at least half of them warriors, were led by Khal Temmo and they sacked and burned every town and city before them (III: 96). When they came to the Free City of Qohor, 3,000 Unsullied eunuch slave-soldiers awaited them. Temmo, his bloodriders, his kos, and all of his sons died with more than 12,000 Dothraki screamers. From that time Qohor has kept a standing guard of Unsullied to guard it, each carrying a black braid of hair on his spear in honor of the Three Thousand (III: 97).