Origanaly, Westeros was inhabited by the Children of the Forest. About 12.000 years before Aegon's landing, the First Men invaded Westeros under the leadership of the First King, crossing The Arm of Dorne, a land bridge connecting Westeros and Essos, located in today's Stepstones(between the Broken Hand and the Disputed Lands.)(AGoT-Bran 7, HBO viewers guide, season 2 Appendix, Westeros Through the Ages).
When the First Men first reached Westeros, they were stronger and bigger than The Children, they were equipped in armors and had bronze swords. Shortly, the First Men started to cut and burn the trees. The Children were annoyed by that, since they worshiped trees, and declared war on the First Men (AGot-Bran 7,The Children of the Forest, the First Men, and the Andals).
Trying to defend their land, the Greenseers (Children with supernatural powers) broke the Arm of Dorne using black magic. As the war continued, the First Men were cutting Weirwood trees, weakening the power of the Greenseers(ACoK-Bran 4) Later, the Children tried to break Westeros in two, by shattering The Neck just like they did with the Arm. However the failed, causing the flooding of the Neck, which is why the Riverlands are full of bogs and swamps(AGoT-Catelyn 8).
Finally, the War ended with The Pact, a peace treaty between the two races, signed in the Isle of Faces. With the signing of the Pact, the Dawn Age had ended and The Age of Heroes had started, a period of peace that lasted for 4.000 years, until the invasion of the White Walkers and The Long Night (AGoT-Bran 7).
We don't know when the Walkers where created but we know that it was during the War between the Children and the First Men, as an attempt of the Children to win, just like with the Shattering of the Arm of Dorne or The Flooding of the Neck.