In the Dawn of Days, the period of history that came to an end (according to tradition) some twelve thousand years ago, humanity did not exist save as small bands of roving tribesmen. From whence they came, no-one could say for certain, not even the elder races.
At that time the world was the domain of two races: the Children of the Forest and the giants. The giants lived in the great northern mountains of Westeros and were strong, fierce and formidable, but lacking in numbers. The Children lived in and under the vast forests that covered most of the Westerosi continent (and, according to some legends, the forests of Essos as well) at that time, sprawling across much of the North, the Riverlands, the Reach and the Stormlands. Neither race recorded history nor wrote books, so it is unknown how long the two races dwelt – sometimes with hostility – alongside one another. According to the Children, their memory stretches back tens and maybe hundreds of thousands of years into a past so remote it is scarcely credible to believe. Some maesters hold that the world is five hundred thousand years old. If so, it may well be that the Children simply ruled the known world for all of that time until men arrived to displace them. The Children lived in harmony with nature, carving faces into the great weirwood trees that could in those days be found in every forest from the Red Mountains to the Frostfangs and enjoying a simple and peaceful existence, only occasionally affected by conflict with the giants.
There are suggestions of some other, ancient forces dominating the world, however. Black stones, made of an unusual, oily substance, have been found scattered across the world from Pyke to Asshai. Mysterious vast mazes, possibly of non-human origin, can be found on the islands of Lorath. Colossal fortifications, potentially too colossal to be of human construction, stretch across the north-eastern borders of Yi Ti. The true origin of these ruins and items remains unknown, but suggest that the real history of the world is far more complex and bizarre than the neat, orderly chronologies that the maesters strive for.
We know that in those remote times, the world looked differently to how it does now. Westeros and Essos were joined by an immense isthmus that separated the Narrow Sea from the Summer Sea, stretching from what is now Dorne into the Disputed Lands in the Heel of Essos. The Sea of Dorne was in those days a large, brackish lake, likely fed by many streams originating in the Red Mountains and the mountainous hills stretching along the coast (which later became the Stepstones). The world was wetter, with the Silver Sea covering what is now a series of broken-up lakes in the western Dothraki Sea, and a vast body of water lying inland in Essos, now a salt desert and a lake collectively called the Shrinking Sea*. The Neck in Westeros was also not covered in swamps, instead consisting of pleasant woodland. There were no cities and very few people of any kind, so no logging, no cities and nature was allowed to dominate.
From where the first tribes of men came is unknown, save that they originated from the east, from Essos where they lived in tribal groupings. Whether they did somehow spring up out of the ground there, or perhaps came from the south, from Sothoryos or from lands as yet unknown in the most distant east, is unknown. They rarely, if ever, came west into Westeros and were not deemed a threat by the Children or the giants.
What changed is that these tribes started settling, raising families and larger social groups. They started farming the land and then started created weapons, first of stone and later of bronze. The creation of bronze spurred a new age of warfare and rivalry between the tribes. Eventually, groups were displaced westwards across the Arm of Dorne in vast numbers, forming both an invasion and a migration. According to traditional histories the First Men began the great crossing to the Sunset Lands over twelve thousand years ago.
* Based on the original cover blurb for A Game of Thrones and hints in The World of Ice and Fire, it is possible to highly probable that the world enjoyed “normal” climatic conditions in these days, seasons of regular length like our own. If this is the case, it is likely that Westeros and Essos would both be much more fertile with smaller deserts (if any), due to the more regular alteration in temperature.