The construction of the Wall happened during a period known as the Age of Heroes, which was about 8000 years before the events of the current story. All that modern Westerosi know about this period are legends passed down through the ages. Westerosi historians have no idea how valid these legends are.
That being said, the legend goes that the Others (AKA the White Walkers) invaded the realms of men in a dread event known as The Long Night. Eventually, the Others were defeated and pushed back into the northern wastes where they came from. Then a man named Brandon the Builder (who also founded the Stark dynasty) built the Wall to prevent the Others from invading the realms of men again. Legends say that he infused the Wall with magic spells to hold it together and prevent the Others from passing through it. The Night's Watch were founded to man the Wall, and they continued working on it. With each subsequent Lord Commander raising the Wall higher than his predecessor. However, at some point, the Night's Watch became too small to continue that and work on the Wall stopped, leaving it at it's current height of 700 feet.